Is this a polyhedron?

Question

Is $S$ a polyhedron?

$$S=\{x\in\mathbb{R}^n|\|x-x_0\|\le\|x-x_1\|\}$$ where $x_0, x_1$ are given. $S$ is the set of points that are closer to $x_0$ than to $x_1$.

I was thinking the answer is yes, since $S$ is a halfspace, but how do I show that $S$ is a halfspace?

Answer 1

Notice $$\|x-x_0\|\le\|x-x_1\| \iff \|x-x_1\|^2 - \|x-x_0\|^2 \ge 0$$ and the quadratic term in the LHS of last expression cancel each other. We find

$$S = \big\{\; x \in \mathbb{R}^n : 2 (x_0 - x_1) \cdot x + \|x_1\|^2 - \|x_0\|^2 \ge 0\;\big\}$$ This is the equation of a half-space.

Answer 2

To get to know this set, we express the norms using inner products. $$ \|x-x_0\|\le\|x-x_1\| \Leftrightarrow \|x-x_0\|^2\le\|x-x_1\|^2 \Leftrightarrow \langle x-x_0, x-x_0 \rangle\le \langle x-x_1,x-x_1\rangle. $$ We have $$ \langle x-x_0, x-x_0\rangle = \langle x,x\rangle - 2\langle x,x_0\rangle + \langle x_0,x_0\rangle, $$ thus our inequality becomes $$ -2\langle x,x_0\rangle+\langle x_0, x_0\rangle \le -2\langle x,x_1\rangle+\langle x_1,x_1\rangle $$ which is equivalent to $$ 0 \le \langle x,2(x_0-x_1)\rangle+\|x_1\|^2-\|x_0\|^2, $$ or even $$ 0 \le \langle x,x_0-x_1\rangle+\frac{1}{2}\left(\|x_1\|^2-\|x_0\|^2\right). $$ For $=$ instead of $\le$ this describes a hyperplane with normal vector $x_0-x_1$ going through the midpoint $\frac{1}{2}(x_0+x_1)$. Therefore our inequality describes a halfspace with the described hyperplane as its boundary.