The probabilistic complexity of the Voronoi diagram of points on a polyhedron
Mordecai J. Golin, Hyeon-Suk Na · 2002
(MATH) It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Θ( n 2 ). Interest has recently arisen as to what happens, both in deterministic and probabilistic situations, when the 3-dimensional points are restricted to lie on the surface of a 2-dimensional object. In this paper we consider the situation when the points are drawn from a 2-dimensional Poisson distribution with rate n over a fixed union of triangles in $\myRe^3.$ We show that with high probability the complexity of their Voronoi diagram is $\Ot n .(MATH) This implies, for example, that the complexity of the Voronoi diagram of points chosen from the surface of a general fixed polyhedron in $\myRe 3 will also be $\Ot n with high probability.