Moving an interior point within a convex hull

Question

Let $p_1,\dots,p_k,q\in\mathbb{R}^n$ such that $q$ is in the convex hull $\mathcal{C}$ of $p_1,\dots,p_k$. Let $q\ne q'\in\mathbb{R}^n$ be another point in $\mathcal{C}$. How do I show that there exists $i\in\{1,\dots,k\}$ such that $\lVert p_i - q'\rVert < \lVert p_i - q\rVert$? Roughly speaking, I wanted to show that moving a point $q$ within $\mathcal{C}$ moves the point closer to some $p_i$.

Answer 1

For the geometric intuition refer to copper.hat's comment. Here is a formal proof: let

$$H = \{ x \in \mathbb{R}^n : \| x - q \| \leqslant \| x - q' \| \}.$$

We will show that $H$ is convex. For this purpose note that

$$\begin{align*} x \in H & \iff \| x - q \|^2 \leqslant \| x - q' \|^2 \\ & \iff \left< x-q, x-q \right> \leqslant \left< x-q', x-q' \right> \\ & \iff \| x \|^2 - 2 \left< x, q \right> + \| q \|^2 \leqslant \| x \|^2 - 2 \left< x, q' \right> + \| q' \|^2 \\ & \iff 2 \left< x, q'-q \right> \leqslant \| q' \|^2 - \| q \|^2 \\ & \iff \left< x, u \right> \leqslant d, \end{align*}$$ where $u = q'-q$ and $d = \frac{\| q' \|^2 - \| q \|^2}{2} = \left< \frac{q'+q}{2}, u \right>$.

Now take any $x, y \in H$ and $\alpha \in [0, 1]$. Then $\left< x, u \right> \leqslant d$ and $\left< y, u \right> \leqslant d$, hence

$$\left< \alpha x + (1-\alpha) y, u \right> = \alpha \left< x, u \right> + (1-\alpha) \left< y, u \right> \leqslant \alpha \cdot d + (1-\alpha) \cdot d = d,$$

and so $\alpha x + (1-\alpha) y \in H$. Therefore $H$ is convex.

Now assume for contradiction that $\| p_i - q \| \leqslant \| p_i - q' \|$ for $i = 1, 2, \ldots, k$. Then $p_1, \ldots, p_k \in H$, so the convex hull of these points is contained in $H$. In particular $q' \in H$, which is a contradiction.