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\|$?
Distance between points in a convex set and outside of a convex set.
2 Answers
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.
-
0@RahulNarain: Thanks! Hope I remember the Latex! – 2012-05-09
As a counter example consider two points in $\mathbb{R}^2$, $W=\{(0,0),\,(2,0)\}$. Clearly $(1,0)$ is in the convex hull $C$ of $W$. The distance from this point to any point in $W$ is 1. However, the point $(1,\varepsilon)\in\mathbb{R}^n \setminus C$ is at a distance of $\varepsilon$ from $(1,0)$. then the statement is false for $-1< \varepsilon < 1$.