The probabilistic complexity of the Voronoi diagram of points on a polyhedron

ABSTRACT

(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 ²). 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 $\Otn.(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³ will also be $\Otn with high probability.

REFERENCES

• 1: D. Attali and J-D. Boissonnat,
• 2: Dominique Attali , Jean-Daniel Boissonnat, A linear bound on the complexity of the delaunay triangulation of points on polyhedral surfaces, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566304]
• 3: Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378636]
• 4: M. J. Golin and Hyeon-Suk Na, "On the Average Complexity of 3D-Voronoi Diagrams of Random Points On Convex Polytopes", Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG00), (2000) 127--135. Extended version accepted in Computational Geometry: Theory and Applications.
• 5: M. J. Golin and Hyeon-Suk Na, "On the Proofs of Two Lemmas Describing the Intersections of Spheres with the Boundary of a Convex Polytope", Hong Kong UST Theoretical Computer Science Center Technical Report HKUST-TCSC-2001-09, July 2001. Available from www.cs.ust.hk/tcsc/RR.
• 6: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms