Are there subsets L in R^n such that it is "easy to find" closest point in L to a given P in R^n ? Vague question motivated by error-correcting codes  Math Motivation: consider LINEAR subspace $L$  in $R^n$ and given vector $E$ in $R^n$, then it is easy to find a closest vector $S \in L$  to $E$ - just ortogonal projection. 
Question Are they some interesting examples/constructions  of non-linear manifolds/subsets $L$ in $R^n$ such that  solve similar question for it  is also "easy" ?
Well, "easy" means - not just direct use of  some minimization algorithm...

Telecom motivation: set $L$ is set of signals which we want to "transmit", the map $L \to R^n$
is "error correcting coding" (i.e. adding redundant information), after the "transmission" due to noise we get point $E$ which might be out of the original set $L$.
The "decoding" is the search of point $S$ in $L$ which is most close to received with errors point $E$. 
So in the language of telecom theory my question is: how to build code which is "easy" to "decode". (At the moment I forget about the other important requirment - that 
code should correct as many errors as  better)

There is clearly huge literature in coding theory. But may be some fresh look "ab initio"
would be helpful (at least to clarify my mind).
 A: Actually I only have  a vague idea of how "easy" the minimization problem should be, and how "large" the class of sets $L.$ Clearly, the optimal balance between these aspects depends on the scopes you have in mind.
The simplest sets $L$, after linear subspaces and of course spheres, are possibly the ellipsoids; although the theory for the corresponding point-set distance problem is clear, a complete solution seems not so cheap to me.
Let $A$ be a positive definite symmetric matrix of order $n$, and let $L$ be the ellipsoid $\{x\in\mathbb{R}^n\, : \, (Ax\cdot x)\le 1 \}$. Let $p\in\mathbb{R}^n$ not in $L$, that is  satisfying $(Ap\cdot p) > 1$. The unique minimizer $x\in L$ of the (squared) distance from $p$, $|x-p|^2$ 
satisfies
$$p-x=\lambda Ax$$
for some Lagrange multiplier $\lambda\ge0$, which is determined by the condition $x\in\partial L$, that is $(Ax\cdot x)= 1$. Since $\lambda\ge0$, the operator $(I+\lambda A)$ is invertible, and we have then $x=(I+\lambda A)^{-1}p$, so $Ax=(I+\lambda A)^{-1}Ap$, and 
$$1=(Ax\cdot x)=\big( (I+\lambda A)^{-2} Ap\cdot p\big )$$
If $A$ has eigenvalues $0\le\alpha_1\le\dots\le\alpha _ n$ and if the coordinates of $p$ in the spectral basis are $p_1,\dots, p _ n$. the latter equation for $\lambda$ may be written
$$1=\sum_{k=1}^n \frac{\alpha_k p_k^2}{(1+\lambda \alpha_ k)^2} $$
The RHS is indeed a strictly decreasing function of $\lambda$, vanishing at infinity, with value $(Ap\cdot p) > 1$ at $\lambda=0$, showing that it has exactly one positive solution $\lambda$, as it has to be. However, I do not know a quick solution of this equation, for all values of $(p_1,\dots p_n)$. Maybe a sub-class of ellipsoids (that is, special values of $\alpha_1,\dots \alpha_n$) do allow nice solutions.
A: From your requirements I cannot understand whether this qualifies: point that realizes
the distance between a closed convex set and a given point (distance for a complete
uniformly convex norm). Perhaps you should be more specific in your question.
Edit: I do not understand the meaning of "easy" for you. But I also know pratically nothing
about coding theory. If you clarify "easy" for your context, perhaps someone else can
give you more useful answers.
