Delaunay triangulations of imprecise pointsin linear time after preprocessing

ABSTRACT

An assumption of nearly all algorithms in computational geometry is that the input points are given precisely, so it is interesting to ask what is the value of imprecise information about points. We show how to preprocess a set of n disjoint unit disks in the plane in O(n log n) time so that if one point per disk is specified with precise coordinates, the Delaunay triangulation can be computed in linear time. From the Delaunay, one can obtain the Gabriel graph and a Euclidean minimum spanning tree; it is interesting to note the roles that these two structures play in our algorithm to quickly compute the Delaunay.

REFERENCES

• 1: Manuel Abellanas , Ferran Hurtado , Pedro A. Ramos, Structural tolerance and delauny triangulation, Information Processing Letters, v.71 n.5-6, p.221-227, Sept. 30, 1999 [doi>10.1016/S0020-0190(99)00107-6]
• 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: Deepak Bandyopadhyay , Jack Snoeyink, Almost-Delaunay simplices: nearest neighbor relations for imprecise points, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 4: Deepak Bandyopadhyay , Jack Snoeyink, Almost-Delaunay simplices: Robust neighbor relations for imprecise 3D points using CGAL, Computational Geometry: Theory and Applications, v.38 n.1-2, p.4-15, September, 2007 [doi>10.1016/j.comgeo.2006.11.003]
• 5: K. Bühler, E. Dyllong, and W. Luther. Reliable distance and intersection computation using finite precision geometry. In Numerical Software with Result Verification, number 2991 in LNCS, pages 160--190. Springer Verlag, 2004.
• 6: J. Cartigny, F. Ingelrest, D. Simplot-Ryl, and I. Stojmenovic. Localized LMST and RNG based minimum-energy broadcast protocols in ad hoc networks. Ad Hoc Networks, 3(1):1--16, 2005.
• 7: Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.
• 8: Bernard Chazelle, Triangulating a simple polygon in linear time, Discrete & Computational Geometry, v.6 n.5, p.485-524, 1991 [doi>10.1007/BF02574703]
• 9: F. Chin, J. Snoeyink, and C. A. Wang. Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom., 21(3):405--420, 1999.
• 10: Francis Chin , Cao An Wang, Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time, SIAM Journal on Computing, v.28 n.2, p.471-486, April 1999 [doi>10.1137/S0097539795285916]
• 11: Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
• 12: J. S. Ely and A. P. Leclerc. Correct Delaunay triangulation in the presence of inexact inputs and arithmetic. Reliable Computing, 6:23--38, 2000.
• 13: S. Fortune. Numerical stability of algorithms for 2-d Delaunay triangulations. Internat. J. Comput. Geom. Appl., 5(1-2):193--213, 1995.
• 14: K. R. Gabriel and R. R. Sokal. A new statistical approach to geographic variation analysis. Systematic Zoology, 18:259--278, 1969.
• 15: Michael T. Goodrich , Joseph S. B. Mitchell , Mark W. Orletsky, Practical methods for approximate geometric pattern matching under rigid motions: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.103-112, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.177572]
• 16: R. L. Graham , B. D. Lubachevsky , K. J. Nurmela , P. R. J. Östergård, Dense packings of congruent circles in a circle, Discrete Mathematics, v.181 n.1-3, p.139-154, Feb. 15, 1998 [doi>10.1016/S0012-365X(97)00050-2]
• 17: D. Salesin , J Stolfi , L. Guibas, Epsilon geometry: building robust algorithms from imprecise computations, Proceedings of the fifth annual symposium on Computational geometry, p.208-217, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73857]
• 18: L. J. Guibas, D. Salesin, and J. Stolfi. Constructing strongly convex approximate hulls with inaccurate primitives. Algorithmica, 9:534--560, 1993.
• 19: A. A. Khanban. Basic Algorithms of Computational Geometry with Imprecise Input. PhD thesis, Imperial College, London, 2005.
• 20: A. A. Khanban and A. Edalat. Computing Delaunay triangulation with imprecise input data. In Proc. 15th Canad. Conf. Comput. Geom., pages 94--97, 2003.
• 21: A. A. Khanban, A. Edalat, and A. Lieutier. Computability of partial Delaunay triangulation and Voronoi diagram. In V. Brattka, M. Schröder, and K. Weihrauch, editors, Electronic Notes in Theoretical Computer Science, volume 66. Elsevier, 2002.
• 22: M. Löffler and M. van Kreveld. Largest and smallest convex hulls for imprecise points. Algorithmica, 2008 (to appear).
• 23: Kurt Mehlhorn , Stefan Näher, LEDA: a platform for combinatorial and geometric computing, Cambridge University Press, New York, NY, 1999
• 24: R. Seidel. A method for proving lower bounds for certain geometric problems. In G. T. Toussaint, editor, Computational Geometry, pages 319--334. North-Holland, Amsterdam, Netherlands, 1985.
• 25: J. R. Shewchuk. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry: Theory and Applications, 22(1-3):21--74, 2002.
• 26: E. Specht. The best known packings of equal circles in the unit circle (up to n = 500). http://hydra.nat.uni-magdeburg.de/packing/cci/cci.html, July 2007.
• 27: K. Sugihara and M. Iri. Two design principles of geometric algorithms in finite-precision arithmetic. Appl. Math. Lett., 2(2):203--206, 1989.
• 28: K. Sugihara and M. Iri. Construction of the Voronoi diagram for 'one million' generators in single-precision arithmetic. Proc. IEEE, 80(9):1471--1484, Sept. 1992.
• 29: M. van Kreveld and M. Löffler. Largest bounding box, smallest diameter, and related problems on imprecise points. In Proc. 10th Workshop on Algorithms and Data Structures, LNCS 4619, pages 447--458, 2007.
• 30: F. Weller. Stability of Voronoi neighborship under perturbations of the sites. In Proc. 9th Canad. Conf. Comput. Geom., pages 251--256, 1997.
• 31: Chee K. Yap, Robust geometric computation, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

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:
data imprecision, delaunay triangulation, gabriel graph, minimum spanning tree