4
$\begingroup$

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?

$\endgroup$
2
6
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.