Prove $C = \left\{ x \in \mathbb R^n : \bigwedge_{i=1}^K \| x - x_0 \|_2 \leq \| x - x_i \|_2 \right\}$ is a convex set

Question

Prove $$C = \left\{ x \in \mathbb R^n : \bigwedge_{i=1}^K \| x - x_0 \|_2 \leq \| x - x_i \|_2 \right\}$$ is a convex set.

Does that mean we have to show that

$$x \mapsto \|x-x_0\|_2 - \|x-x_i\|_2$$

is a convex function? Any help? Thanks a lot.

Answer 1

I'm presuming $x_0, \ldots, x_K$ are given distinct points of $\mathbb R^n$.
Note that for two points $a \ne b$,$\|x - a\| \le \|x - b\|$ iff $x \cdot (b-a) \le \frac{a+b}{2} \cdot (b-a)$. That is, the points where $\|x-a\| = \|x-b\|$ consist of a hyperplane through the midpoint of $a$ and $b$, orthogonal to $b-a$, and you want the points on or on one side of that hyperplane.

Answer 2

It means you have to prove that if $x_1,x_2\in C$ then $y:=\lambda x_1+(1-\lambda)x_2\in C$, where $\lambda$ is any number in $(0,1)$.

To do that suppose (without loss of generality) that $||x_1-x_0||_2$ is bigger than $||x_2-x_0||_2$. Then, using the triangular inequality, \begin{align*} ||y-x_0||_2=&\,||\lambda(x_1-x_0)+(1-\lambda)(x_2-x_0)||_2\\ \leq&\,\lambda||x_1-x_0||_2+(1-\lambda)||x_2-x_0||_2\\ \leq&\,\lambda||x_1-x_0||_2+(1-\lambda)||x_1-x_0||_2\\ =&\,||x_1-x_0||_2. \end{align*} As $x_1$ belongs to $C$ this implies that $y$ belongs to $C$ as well, and you are done.