# Distance between points in a convex set and outside of a convex set.

Let $W$ be a set of points in $\mathbb{R}^n$. Let $C$ be the convex hull of the members of $W$. Is there a simple way of demonstrating that for any $x \in C$ and any $y \in \mathbb{R}^n \backslash C$, there must be some $w \in W$ such that $\|w - x\| < \|w - y\|$?

-

Let $H=\{ z | \langle z,x-y\rangle = \frac{1}{2} (||x||^2-||y||^2)\}$ Then $H$ is a hyperplane perpendicular to $x-y$, that passes through $\frac{1}{2}(x+y)$.

Let $S$ be the half-space containing $x$, ie, $S=\{ z | \langle z,x-y\rangle \geq \frac{1}{2} (||x||^2-||y||^2)\}$. Note that $x \in S^{\circ}$. Also, note that if $z \in S^{\circ}$, then $||z-x|| < ||z-y||$.

Finally, since $x \in C$, we can write $x = \sum_{i=1}^k \lambda_i w_i$, with $w_i \in W$ and $\lambda_i$ are convex multipliers. Then at least one $w_{i'} \in S^{\circ}$, since $\langle x,x-y\rangle = \sum_{i=1}^k \lambda_i \langle w_i,x-y\rangle > \frac{1}{2} (||x||^2-||y||^2)$. Consequently, $||w_{i'}-x|| < ||w_{i'} -y||$, which is what you wanted to show.

-
Thanks. Two questions about notation. First, is: <x, y> the dot product of x and y? Second, what operation does the raised dot indicate? I.e., what set is S$^0$? –  Mike C May 8 '12 at 22:12
Yes, it is the dot (inner) product. The notation means the interior of the set. –  copper.hat May 8 '12 at 22:59
Cool. Thanks again! –  Mike C May 9 '12 at 0:05
I edited your answer to replace $<, >$ with $\langle, \rangle$. Hope that's OK. –  Rahul May 9 '12 at 0:06
@RahulNarain: Thanks! Hope I remember the Latex! –  copper.hat May 9 '12 at 0:16