# Does Voronoi tessellation in 3D always produce convex polyhedrons?

I'm more or less certain that the Voronoi tessellations (using Euclidean distance measure) produce convex polygons/polyhedrons. Is there a way to prove this mathematically? Or am I wrong? I am especially interested in 3D case. On a side note, can a convex polyhedron have a concave face?

-
If it has a concave face, then the 2 points which make the face not convex, will fail the definition of a convex polyhedron. Hence, no to side note. –  Calvin Lin Jan 3 '13 at 5:31
@Calvin: As I understand the question, that's not true. 'Concave face' presumably means concave as a 2-dimensional polygon. So the line between your two points could be contained in the polyhedron. I think your conclusion is correct, but I don't think you have proved it. –  TonyK Jan 3 '13 at 9:07
@TonyK Yes you're right. It could have a protrusion. Like 3-D Pac-man with a wide beak. –  Calvin Lin Jan 3 '13 at 16:23
Can we prove this please (convex polyhedrons have all convex faces)? –  John Smith Jan 3 '13 at 21:07

Assuming all your sites $P_k$ are points, the definition of the $k$th Voronoi cell $$R_k = \{x \in X\,\, | \,\,d(x,P_k) \leq d(x, P_j)\,\, \text{for all}\,\, j\neq k\}$$ reduces to an intersection of half-spaces, because $d(x,P_k)\le d(x,P_j)$ if and only if $\langle x-P_k,P_j-P_k\rangle\le\frac12\lVert P_j-P_k\rVert^2$, that is, $x$ lies on the side closer to $P_k$ of the plane perpendicularly bisecting the line segment between $P_k$ and $P_j$. This makes it a convex polyhedron (assuming your definition of polyhedron includes unbounded sets).