2

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?

John Smith
  • 185
  • 3
    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 03 '13 at 05: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 03 '13 at 09:07
  • @TonyK Yes you're right. It could have a protrusion. Like 3-D Pac-man with a wide beak. – Calvin Lin Jan 03 '13 at 16:23
  • Can we prove this please (convex polyhedrons have all convex faces)? – John Smith Jan 03 '13 at 21:07

1 Answers1

3

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

  • Can we also prove this just from the definition of convexity, that is, if $d(x, P_k) \le d(x, P_j)$ and $d(y, P_k) \le d(y, P_j)$ for all $j \ne k$, then $d(\lambda x + (1 - \lambda) y, P_k) \le d(\lambda x + (1 - \lambda) y, P_j)$ for all $j \ne k$? – ViktorStein Oct 08 '22 at 12:16