# 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. – Rahul 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. – Rahul Jan 12 '13 at 6:38
Just a slightly different approach to the key Lemma 3: Pick a ball $B$ around $x$ small enough, so that for all $y\in B$, the ray $yP(y)$ is almost parallel to $xP(x)$. Suppose it's pointing south. Now let $y$ run on the 45N latitude, so that the segment $yP(y)$ intersects the equator at $Q(y)$ (say). Since $yP(y)$ are nearly parallel, the winding number of $Q(y)$ around $x$ is 1. Now let $y$ run on higher and higher latitudes, until it reaches the North pole. The winding number must jump to 0 somewhere in the process, at which time $Q(y)=x$, i.e., $x\in yP(y)$. The rest is the same as above. – Fan Zheng Mar 12 '15 at 1:38

It's true in Euclidean space, but not in general unless $K$ is weakly closed. You can see a proof for Euclidean space here
the answer is no! Let $H=\mathbb R$ (real numbers), and take $K=[1,2]\cup [3,4]$. ($\cup$ means union) then K has the closest point property while it is not convex!
What about the point $2.5$ whose nearest points are $2$ and $3$. – Mike F May 22 '14 at 16:48