On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes (Q1873689)

The authors study the complexity (that is, number of vertices, edges and faces) of Voronoi diagrams of points distributed on a 2-dimensional manifold in 3-dimensional space. It is known that the expected complexity for \(n\) points independently and uniformly distributed in a 3-D region is \(O(n)\), but it may be as bad as \(O(n^2)\) if these points lie on a 1-dimensional submanifold. It is proved that for 2-D manifolds the expected complexity is still \(O(n)\). This fact is established for Poisson distribution, although the authors claim that a standard modification allows to extend it to uniform distribution. The proof is very geometrical and nicely illustrated. For detailed proofs of two technical lemmas the reader is referred to a report available on the web.