A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time

ABSTRACT

We present a modification to the divide-and-conquer algorithm of Guibas & Stolfi [GS] for computing the Delaunay triangulation of n sites in the plane. The change reduces its &THgr;(n log n) expected running time to &Ogr;(n log n) for a large class of distributions which includes the uniform distribution in the unit square. The modified algorithm is significantly easier to implement than the optimal linear-expected-time algorithm of Bentley, Weide & Yao [BWY]. Unlike the incremental methods of Ohya, Iri & Murota [OIM] and Maus [M] it has optimal &Ogr;(n log log n) worst-case performance. The improvement extends to the composition of the Delaunay triangulation in the Lp metric for 1 < p ≤ ∞. Experimental evidence presented demonstrates that in the Euclidean case the modified algorithm performs very well for n ≤ 216, the range of the experiments. We conjecture that its average running time is no more than twice optimal for n less than seven trillion.

REFERENCES

• BWY: Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
• F: S Fortune, A sweepline algorithm for Voronoi diagrams, Proceedings of the second annual symposium on Computational geometry, p.313-322, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10549]
• GS: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• H: F. K. Hwang, An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees, Journal of the ACM (JACM), v.26 n.2, p.177-182, April 1979 [doi>10.1145/322123.322124]
• L: D. T. Lee, Two-Dimensional Voronoi Diagrams in the Lp-Metric, Journal of the ACM (JACM), v.27 n.4, p.604-618, Oct. 1980 [doi>10.1145/322217.322219]
• LS: D. T. I,cc & B. S(:hachtcr, "Two algo,'ithms for constructing D(;1;u}Emy triangulatioim," Int. J. Comput. /nform. Sci. 9 (1980), 219- 242.
• LW: D. T. Lee & C. K. Wong, "Voronoi diagrams in L1 (Loo) metrics with twodimensional storage applications," SIAM J. Coml)ut. 9 (1980), 200--211.
• M: A. Maus, "Dclaunay triangtllation and the convex hull of n points in expected linear time," BIT 24 (1984), 151-163.
• OIM: T. Ohya, M. Iri & K. Murota, "Improve-' mcnts of the incremental methods for the Voronoi diagram with computational compa,'ison of various algorithms," J. Operations' Research Soc. Japan 27 (1984), 306--336.
• S: R. Sibson, "Locally equiangular triangulations,'' Comput. J. 21 (1978), 243-245.
• SG: R. Sibson & P. J. Green, "Computing' Dirichlet tessellations in the plane," Comput. j. 21 (1978), 168-173.
• Sh: Michael Ian Shamos, Computational geometry., 1978

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

General Terms:
Algorithms, Experimentation, Performance, Theory, Verification