Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
    
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
1  
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

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
    
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 answer is no! Let H=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!

share|improve this answer
    
What about the point $2.5$ whose nearest points are $2$ and $3$. –  Mike F May 22 at 16:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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