Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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 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
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.