I have been asked to prove that a Voronoi region $V=\{x \in \mathbb{R}^n : \|x-x_0\| \le \|x-x_i\|, i=1,\dots,k\}$ around $x_0$ with respect to $x_1,\dots,x_k$ is a polyhedron.
My idea is to find the set of hyperplanes $h_i : a_i^Tx=b_i$ defined by the pairs $(x_0,x_i)$, such as they divide the entire space in halfspaces that fulfill $a_i^Tx \le b_i \Leftrightarrow \|x-x_0\| \le \|x-x_i\|$.
Intuitively, I can see that the hyperplanes I am looking for are symmetric with respect to each pair of points, so $a_i = x_i-x_0$ and $b_i = (x_i-x_0)^T (\frac{x_i+x_0}{2})$ could be a valid solution. As always, I am able to imagine it in a visual way, but I think I have no idea of how could I try to prove it in a more formal way, that is, to derive the valid $a_i$ and $b_i$ values without drawing.
Added: Following the Boyd and Vanderberghe book on convex optimization, the definition of polyhedron I am using is that of a intersection of a finite number of halfspaces and hyperplanes.
Could anybody please give me a hint on whether this is possible or not? Could a graphical proof like this just do its job?
Thanks in advance.
Best Answer
Your hyperplane is correct. If you square the right-hand inequality of your equivalence and cancel the terms $x^Tx$ on both sides, you're left with a linear equation for $x$ that you can bring into the form of the left-hand inequality with the values for $a_i$ and $b_i$ that you gave. Given the definition you cite, that completes the proof. Note, however, that there are other definitions of polyhedra which imply that polyhedra are bounded. The Wikipedia article states that polyhedra are bounded but has a section discussing the relationship to the definition you cite.