# Is a closed set with the “unique nearest point” property convex?

A friend of mind had a question that I couldn't answer. It is well-known that if $K$ is a closed, convex subset of a Hilbert space $H$ (say over the reals) then, for any point $p \in H$, there exists a unique point $p'$ in $K$ closest to $p$. We would like to know whether the following converse is true.

If $K \subset H$ is a closed subset such that, for all points $p \in H$, there exists a unique point $p' \in K$ closest to $p$, does it follows that $K$ is convex?

I'm not sure what the answer is - even when $H$ is the plane!

OK, I found some time to read/understand the document that Michael Biro linked below, so I thought I would add a summary. In what follows, $K$ is a subset of the finite-dimensional Hilbert space $\mathbb{R}^n$ such that, for all $x \in \mathbb{R}^n$, there is a unique $P(x) \in K$ as close as possible to $x$. That is, $P(x)$ is the only point in $K$ with $\| x-P(x)\| = \mathrm{dist}(x,K)$. In particular, $\mathrm{dist}(x,K)$ is positive when $x \notin K$, so $K$ is clearly closed. Another easy observation is given below.

Lemma 1. If $x \in \mathbb{R}^n \setminus K$, then $P(y) = P(x)$ for all $y$ on the line segment joining $x$ to $P(x)$.

Proof. We have $$\|x - P(y)\| \leq \|x - y\| + \|y - P(y)\| \leq \|x-y\| + \|y-P(x)\| = \|x - P(x)\|$$ whence $P(y) = P(x)$. The final equality above uses the assumption that $y$ is on the line segment joining $x$ to $P(x)$.

It is reasonable to expect Lemma 1 to hold when $y$ is merely on the ray extending from $P(x)$ through $x$. This is true, but far less simple to prove. In fact, the proof seems to need the Brouwer fixed point theorem. To apply Brouwer, we shall need continuity of the projection.

Lemma 2. $P$ is continuous.

Proof. Suppose $x_n \to x$ in $\mathbb{R}^n$. We want to show $P(x_n) \to P(x)$. Note the $P(x_n)$ are clearly at least bounded. Use the Bolzano-Weierstrass theorem to reduce proving $P(x_n) \to P(x)$ to proving $P(x_{n_k}) \to P(x)$ for every subsequence such that $P(x_{n_k})$ converges. If $P(x_{n_k}) \to y \in K$, then $$\|x-y\| = \lim_{k \to \infty} \|x_{n_k} - P(x_{n_k})\| = \lim_{k \to \infty} \mathrm{dist}(x_{n_k}, S) = \mathrm{dist}(x,K)$$ which implies $y=P(x)$.

We now use the Brouwer fixed point theorem to improve Lemma 1.

Lemma 3. If $x \in \mathbb{R}^n \setminus K$, then $P(y) = P(x)$ for all $y$ on the ray extending from $P(x)$ through $x$.

Proof. Suppose the whole ray does not project to $P(x)$. Using Lemmas 1 & 2, argue that $x$ can be moved out along the ray until everything on the closed segment from $P(x)$ to $x$ projects to $P(x)$, but everything further out on the ray does not project to $P(x)$. Let $B$ be a closed ball centred on $x$ disjoint from $K$. Define a map $\Phi : B \to \partial B$ by sending $y \in B$ to the unique point $\Phi(y) \in \partial B$ such that $x$ is on the segment joining $P(y)$ to $\Phi(y)$. It is easy to derive an explicit formula and continuity of $\Phi$ follows from Lemma 2. By Brouwer, $\Phi$ has a fixed point. It turns out there can only be one fixed point and we will say exactly what it is. Suppose that $y$ is a fixed point of $\Phi$. Then $x$ is on the segment from $P(y)$ to $y=\Phi(y)$ so $P(y) = P(x)$ by Lemma 1. But, this determines $y$ uniquely to be the point on $\partial B$ antipodal to $P(x)$. But, now we have a contradiction since this $y$ is beyond $x$ on the ray from $P(x)$ through $x$ and should therefore have $P(y) \neq P(x)$ by assumption.

With Lemma 3 out of the way, it is easy to prove Motzkin's theorem using the idea in Rahul's comment below.

Motzkin's Theorem. Every subset of $\mathbb{R}^n$ with the "unique nearest point property" is convex.

Proof. Suppose that $x \in \mathbb{R}^n \setminus K$. By Lemma 3, for any point $y$ on the ray from $P(x)$ through $x$, we have $P(x) = P(y)$ so that the open ball $B_y$ centred on $y$ with $P(x)$ on the boundary is disjoint from $K$. As $y$ becomes unbounded, we see that $K$ is separated from $x$ by the half-plane through $P(x)$ with normal vector $x-P(x)$. Obviously this precludes the possibility that $x$ is a convex combination of two points in $K$.

• When $K=(x,e^{-x})$, the set is closed but $K$ isn't convex, right? I'm using the idea that convex is where any two points can be joined by a straight line contained in $K$... Is this right or wrong? – anon271828 Jan 9 '13 at 23:08
• Initial thoughts: Take $p\not\in K$ with closest point $p'\in K$, and let $n=p-p'$. From uniqueness, it should follow that $p'$ is also the closest point for all $q=p+\lambda n$ with $\lambda>0$. As $\lambda\to\infty$, this gives a hyperplane through $p'$ normal to $n$ that $K$ must lie entirely to one side of. – user856 Jan 9 '13 at 23:08
• @Rahul: Very astute. This is precisely the idea of the proof under Michael Biro's link. I'm writing up a short summary right now. – Mike F Jan 11 '13 at 5:37
• On StackExchange, answering your own question is not only allowed but encouraged. So you could have posted your edit as an answer, and let the question stay as an actual question. – user856 Jan 12 '13 at 6:38
• – user147263 Jun 2 '16 at 7:55

It's true in Euclidean space, but not in general unless $K$ is weakly closed. You can see a proof for Euclidean space here

• Thanks! I will read this tomorrow. – Mike F Jan 10 '13 at 0:55
• So what's the counterexample? – Nate Eldredge Jan 12 '13 at 5:26
• I think it's still a conjecture for infinite dimensional Hilbert spaces, but there's an example of a non-convex Chebyshev set in an (incomplete) inner product space. sciencedirect.com/science/article/pii/S0021904583710580 – Michael Biro Jan 12 '13 at 6:19
• The link is dead. – user147263 Jun 17 '16 at 0:57

It is true for "finite-dimensional" Euclidean spaces and other special cases (e.g. real Hilbert space with boundedly compact subset $K$). However, this does not hold in general. The following paper provides a construction of a non-convex set with the nearest point property:

Johnson, Gordon G. "A nonconvex set which has the unique nearest point property." Journal of approximation theory 51.4 (1987): 289-332.

Hope this helps!

• Thanks for the reference, +1. Note, however, that, in the comment section of his answer, Michael Biro already gave a link to a paper of Jiang M. which discusses Johnson's paper (and apparently gives some corrections). – Mike F Mar 26 '18 at 19:29