Self-improving algorithms for delaunay triangulations

ABSTRACT

We study the problem of two-dimensional Delaunay triangulation in the self-improving algorithms model [1]. We assume that the n points of the input each come from an independent, unknown, and arbitrary distribution. The first phase of our algorithm builds data structures that store relevant information about the input distribution. The second phase uses these data structures to efficiently compute the Delaunay triangulation of the input. The running time of our algorithm matches the information-theoretic lower bound for the given input distribution, implying that if the input distribution has low entropy, then our algorithm beats the standard Ω(n log n) bound for computing Delaunay triangulations.

Our algorithm and analysis use a variety of techniques: ε-nets for disks, entropy-optimal point-location data structures, linear-time splitting of Delaunay triangulations, and information-theoretic arguments.

REFERENCES

• 1: Nir Ailon , Bernard Chazelle , Seshadhri Comandur , Ding Liu, Self-improving algorithms, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.261-270, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109587]
• 2: A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
• 3: Sunil Arya , Theocharis Malamatos , David M. Mount , Ka Chun Wong, Optimal Expected-Case Planar Point Location, SIAM Journal on Computing, v.37 n.2, p.584-610, May 2007 [doi>10.1137/S0097539704446724]
• 4: Bernard Chazelle, An optimal algorithm for intersecting three-dimensional convex polyhedra, SIAM Journal on Computing, v.21 n.4, p.671-696, Aug. 1992 [doi>10.1137/0221041]
• 5: Chazelle, B., Devillers, O.,Hurtado, F., Mora, M., Sacristan, V., Teillaud, M. Splitting a Delaunay Triangulation in Linear Time, Algorithmica 34, 2002, 39--46.
• 6: Kenneth L. Clarkson , Kasturi Varadarajan, Improved Approximation Algorithms for Geometric Set Cover, Discrete & Computational Geometry, v.37 n.1, p.43-58, January 2007 [doi>10.1007/s00454-006-1273-8]
• 7: Jiří Matoušek , Raimund Seidel , E. Welzl, How to net a lot with little: small &egr;-nets for disks and halfspaces, Proceedings of the sixth annual symposium on Computational geometry, p.16-22, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98530]

INDEX TERMS

Primary 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

General Terms:
Algorithms, Theory

Keywords:
delaunay triangulations