Does Voronoi tessellation in 3D always produce convex polyhedrons?

Question

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?

Answer 1

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).