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)=(I+\lambda A)^{-2}(Ap\cdot p)$$ 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. 2 m; edited body 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. We 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)=(I+\lambda A)^{-2}(Ap\cdot p)$$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. 1 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. We have then x=(I+\lambda A)^{-1}p, so Ax=(I+\lambda A)^{-1}Ap, and$$1=(Ax\cdot x)=(I+\lambda A)^{-2}(Ap\cdot p)$$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.