7
$\begingroup$

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.

  • 0
    @ChristianBlatter, I'll edit the question to include the definition of polyhedron. Thank you.2011-10-05

2 Answers 2

6

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.

  • 1
    @Fernandez: OK; in that case, you're done. I've edited my answer in response to your comment and edit.2011-10-05
1

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.

  • 1
    @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 :-)2011-10-05