Convex Sets and Nearest Neighbors

Question

For a set $S \subseteq \mathbb{R}^n$ and a point $x \in \mathbb{R}^n$, let $c_S(x)$ be the point $s \in S$ that minimizes $\|x-s\|$ if such a point exists and is unique. It is known that $c(x) = s$ exists and is unique if $S$ is closed and convex. My question is: is this "if and only if"? More precisely: Are the following statements equivalent:

1. $S$ is closed and convex.
2. $c_S(x)$ is well-defined for all $x \in \mathbb{R}^n$.

If $S$ is not closed, then there are points that do not have a nearest neighbor in $S$. If $S$ is closed, then, for every $x \in \mathbb{R}^n$, there exist points that are nearest neighbors to $x$. Thus, the question boils down to the following: Let $S \subseteq \mathbb{R}^n$ be closed. Then the following two statements are equivalent:

1. $S$ is convex.
2. For every $x \in \mathbb{R}^n$, there is a unique element $s \in S$ that minimizes $\|x-s\|$.

Is this true?

Answer 1

This is the celebrated Chebyshev problem. The answer is positive in $\mathbb{R}^n$, and still open in the Hilbert space.

Answer 2

A nonempty set $S$ in a normed linear space $X$ is called a Chebyshev set if for each $u \in X$ there is exactly one nearest point in $S$ to $u$ (i.e., for a Chebyshev set, nearest points always exist, and they are unique).

For finite dimensional spaces it is known that:

Theorem. A nonempty set in the Euclidean space $R^n$ is Chebyshev if and only if it is closed and convex.

In infinite dimensions the situation is much more subtle (and some aspects are still open).

Please have a look at this really nice overview talk which explains this, provides references to the state-of-the-art.