I was thinking about the following problem:
Let $\gamma \subset \mathbb R ^2$ be a curve that admits a $C ^{\infty}$ regular parametrization. Is it always possible to choose an open set $E$ containing $\gamma$ such that for all $x\in E$ there is one and only one $q\in \gamma$ such that $|x-q|$ is minimized?
A generalization of the problem is, given a $C^{\infty}$ manifold $M\subset \mathbb R ^n$, does it always exist an open set $E$ containing $M$ with that nice property?
I'm not sure how to tackle the problem, any help is appreciated.
The curve should be embedded, meaning that it's parametrization is a homeomorphism, not just an immersion. For example, this injective immersion is not an embedding, and there is no $E$:
For embedded submanifolds, the statement is true (in all dimensions), and the smoothness assumption can be weakened to $C^2$ (but no further). It's a part of a standard theorem in differential geometry textbook: search Google Books for "tubular neighborhood". I'll give a proof for the special case you stated, a curve $\gamma$ in $\mathbb R^2$.
It suffices to show that every point $p$ has a neighborhood $N_p$ such that for every $z\in N$ there is a unique $q\in \gamma$ that minimizes $|z-q|$. Indeed, the desired $E$ is obtained as $\bigcup_{p\in \gamma} N_p$.
Since $\gamma$ is embedded, there is a neighborhood $U$ of $p$ such that the intersection $\gamma\cap U$ is close to a straight line. Namely, choosing a coordinate system with $p$ as the origin, and with the tangent line as the $x$-axis, we'll have that $\gamma\cap U$ is the graph of some function $y=f(x)$, with $f'(0)=f(0)=0$.
Taking a smaller neighborhood $V$, we ensure that every point of $V$ is closer to $\gamma$ than to $U^c$. This allows us not to worry about the points of $\gamma\setminus U$: they will not be closest to anything in $V$. We just have to show that there is a unique nearest point of $\gamma\cap U$. Observe that if $q$ is nearest to $z$, then $z$ lies on the normal line through $q$. Thus, we must prove that normal lines do not intersect in some neighborhood of $p$.
In terms of the aforementioned coordinates, the normal line to $\gamma$ at $(x,f(x))$ has slope $-1/f'(x)$, hence its parametric equation is $$t\mapsto (x-tf'(x), f(x)+t)$$ The Jacobian of the map $\Phi(x,t) = (x-tf'(x), f(x)+t)$ is $$D\Phi(x,t) = \begin{pmatrix} 1-t f''(x) & -f'(x) \\ f'(x) & 1\end{pmatrix} \tag{1}$$ The matrix (1) has continuous entries, and is the identity matrix when $x=t=0$. Hence, the inverse function theorem applies to $\Phi$ and says that $\Phi$ is a diffeomorphism in some neighborhood of $(x,t)$. Geometrically, this says: if we start near $p$ and follow normal lines for some short distance, they do not intersect. Which was to be proved.
The proof of the general case follows the same strategy.