Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This work is the first to validate theoretically the suspicions of many researchers — that the “average” Voronoi diagram is combinatorially quite simple and can be constructed quickly. Specifically, assuming that dimension d is fixed, and that n input points are chosen independently from the uniform distribution on the unit d-ball, it is proved that the expected number of simplices of the dual of the Voronoi diagram is &THgr;(n) (exact constants are derived for the high-order term), and a relatively simple algorithm exists for constructing the Voronoi diagram in &THgr;(n) time. It is likely that the methods developed in the analysis will be applicable to other related quantities and other probability distributions.

REFERENCES

• 1: D. Avis and B. K. Bhattacharya. Algorithms for computing &dimensional Voronoi diagrams and their duals. In F. P. Preparata, editor, Advancer in Computing Research: Computational Geometry, pages 159-180, Greenwich, Conn., 1983. JAI Press IIlC.
• 2: B. Bhattacharya. Worst-case analysis of a convex hull algorithm. Simon Fraser U., 1982.
• 3: A. Bowyer. Computing Dirichlet tessellations. Computer J., 24(2):162-1661981.
• 4: Kevin Quentin Brown, Geometric transforms for fast geometric algorithms, 1979
• 5: W. Browstow, J.-P. Dussault, and B. L. Fox,Construction of Voronoi polyhedra. J. Computational Physics, 29:81-97, 1978.
• 6: Donald R. Chand , Sham S. Kapur, An Algorithm for Convex Polytopes, Journal of the ACM (JACM), v.17 n.1, p.78-86, Jan. 1970 [doi>10.1145/321556.321564]
• 7: R. A. Dwyer. A faster divide-and-conquer algorithm for constructing Delaunay triangulations. AZgotilhmica, 2(2):137-151, 1987.
• 8: R. A. Dwyer. On the convex huBof random points in a polytope. J. Appl. Prob., 25(4):688-699,1988.
• 9: B. Efron. The convex hull of a random set of points. Biometriha, 52:331-342, 1905.
• 10: J. L. Finney. A procedure for the construction of Voronoi polyhedra. J. Computational Physics, 32:137-143, 1979.
• 11: E. N. Gilbert. Random subdivisions of space into crystals. Ann. Math. Stat., 333958-972, 1962.
• 12: A. Maus. Delaunay triangulation aud the convex hull of n points in expected linear time. BIT, 24:151-163, 1984.
• 13: J. L. Meijering. Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philip8 Rea. Rep., 8:270-290, 1953.
• 14: R. E. Miles. Isotropic random simplices. Adv. Appl. Prob., 3:353-382, 1971.
• 15: II. Raynaud. Sur 1'enveIlope convexe des nuages des points alCatoires dans r", I. J. Appl. Prob., 7:35-48, 1970.
• 16: R. Seidel. Th e complexity of Voronoi diagrams in higher dimensions. In Proc. 20th Annual Alkrton Conference on Communication, Control, and Computing, pages 94-95. University of Illinois at Urbana-Champaign, October 1982.
• 17: R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
• 18: R. Seidel, On the number of faces in higher-dimensional Voronoi diagrams, Proceedings of the third annual symposium on Computational geometry, p.181-185, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41977]
• 19: G. Swart. Finding the convex hulI facet by facet. J. Algorithm, 6:17-48, 1985.
• 20: M. Tanemura, T. Ogawa, and N. Ogita. A new algorithm for three-dimensional Voronoi tessellation. J. Compututional Physics, 51(2):191-207, August 1983.
• 21: A. II. Thiessen. Precipitation averages for large areas. Monthly Weather Review, 39:1082-1084, July 1911.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Finite element methods
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification