# Voronoi region as a polyhedron

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?

-
You are not asked to compute the relevant data of $V$ but to prove that $V$ is a polyhedron. This proof depends on your definition of a polyhedron and general theorems you have at your disposal. – Christian Blatter Oct 5 '11 at 8:00
I'm a little bit curious about the following: A polyhedron apparently doesn't need to be bounded here? Say, if $x_0$ is not 'completely surrounded' by the other points, then the Voronoi region may 'escape to the infinity'. This is irrelevant to the question. I have just seen Voronoi regions of (full rank) lattices, where this is never an issue. – Jyrki Lahtonen Oct 5 '11 at 8:23
@Jyrki, in the Boyd book, which is the one I am using, first defines polyhedron as the intersection of a finite number of halfspaces and hyperplanes, then states that it is convex, and finally talks about the difference between bounded and unbounded ones, specially about its nomenclature when mixing the concepts of polyhedra and polytopes. – Fernandez Oct 5 '11 at 9:03
@ChristianBlatter, I'll edit the question to include the definition of polyhedron. Thank you. – Fernandez Oct 5 '11 at 9:04

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.

-
Thank you, Joriki. From the Boyd book, I have the definition of a polyhedron as the intersection of a finite number of halfspaces and hyperplanes. I was trying to figure the nature of every halfspace generated for each of the hyperplanes I talked about in my question. Then, if I am able to characterize those hyperplanes and associated halfspaces, I thought I could be able to argue that, given a point in the Voronoi region, it would be in one of those halfspaces, and viceversa. – Fernandez Oct 5 '11 at 8:59
@Fernandez: OK; in that case, you're done. I've edited my answer in response to your comment and edit. – joriki Oct 5 '11 at 9:49

I think that you are on the right track. AFAICT your equation defines the hyperplane that bisects the line segment from $x_0$ to $x_i$, and also gives you the constraint for a point to belong to the Voronoi region. You can argue as follows. Let $x$ be an arbitrary point. We can write $x-x_0=x'+ka_i$ for some constant $k$ and some vector $x'\perp a_i$. Then $$\|x-x_0\|^2=\|x'\|^2+k^2\|a_i\|^2$$ by Pythagorean theorem. But here $x-x_i=x-x_0-a_i=x'+(k-1)a_i$, and therefore $$\|x-x_i\|^2=\|x'\|^2+(k-1)^2\|a_i\|^2.$$ We can thus conclude that $$\|x-x_0\|\le \|x-x_i\|\Leftrightarrow k^2\le (k-1)^2\Leftrightarrow k\le\frac12.$$ This means exactly that $x$ is on the same side of the hyperplane $h_i$ as $x$. In other words, the vector $ka_i$ is the orthogonal projection of $x-x_0$ onto the vector $a_i$, and if the projection is on the nearer side of the midway point, we have the desired inequality between the distances.

-
That's rather a roundabout way of doing it :-) – joriki Oct 5 '11 at 8:24
This calculation is meant to be a substitute to the visually obvious fact that this hyperplane splits the space into two sets: one consisting of points closer to $x_0$ the other of points closer to $x_i$. If you wanted something else, then I apologize. – Jyrki Lahtonen Oct 5 '11 at 8:27
@joriki Yeah, I may have misunderstood, which step the OP had problems with. Leaving this here for now, and wait for comments from Fernandez. Prepared to delete :-) – Jyrki Lahtonen Oct 5 '11 at 8:29
I didn't mean to substitute it by the visually obvious fact; I meant that the argument is quite a bit more complicated than the direct transformation I sketched in my answer. – joriki Oct 5 '11 at 8:30
@Fernandez Thanks for the kind comment. Of course, joriki's approach is cleaner, and should get the preference. I also had a picture in my mind. In that picture the 'coordinate' difference from $x$ to $x_0$ vs $x_i$ agree at $n-1$ coordinates, and disagree at only one. I was just porting that image to a calculation :-) – Jyrki Lahtonen Oct 5 '11 at 10:12
show 1 more comment