Numerical stability of algorithms for 2D Delaunay triangulations

ABSTRACT

We show that two Delaunay triangulation algorithms, a diagonal-flipping algorithm and an incremental algorithm, can be implemented in approxiamte arithmetic. The two algorithms have worst-case running time O(n2) on a set of n sites. The correctness assertion is that the algorithms produce a triangulation of the set of sites so that each triangle has an “almost empty” circumcircle, i.e., a circumscribing pseudocircle slightly contracted from the circumcircle contains no sites in its interior.

REFERENCES

• 1: Germund Dahlquist , Ake Bjorck, Numerical Methods, Dover Publications, Incorporated, 2003
• 2: S. Fortune, A sweepline algorithm for Voronoi diagrams. Algoriihmica 2:153-174 (1987).
• 3: S. Fortune, Stable maintenance of point-set triangulation in two dimensions. An abbreviated version appeared in 30th FOC$, pp. 494-499, 1989.
• 4: S. Fortune, Computational Geometry, Directions in Geometric Computing, Information Geometers, R. Martin, ed., to appear, 1992.
• 5: P. Green, R. Sibson. Computing Dirichlet tesseilations in the plane. Computing J. 21:168-173, 1977.
• 6: 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]
• 7: Christoph M. Hoffmann, The Problems of Accuracy and Robustness in Geometric Computation, Computer, v.22 n.3, p.31-40, March 1989 [doi>10.1109/2.16223]
• 8: C.L. Lawson, Software for C1 surface interpolation, Mathematical Software III 161-194, J.R. Rice, ed., Academic Press, 1977.
• 9: Victor J. Milenkovic, Verifiable implementation of geometric algorithms using finite precision arithmetic, Artificial Intelligence, v.37 n.1-3, p.377-401, Dec. 1988 [doi>10.1016/0004-3702(88)90061-6]
• 10: Victor Joseph Milenkovic, Verifiable implementations of geometric algorithms using finite precision arithmetic, 1988
• 11: K. Sugihara, M. Iri, Geometric algorithms in finite-precision arithmetic, Research Memorandum RMI 88-10, University of Tokyo, September, 1988.
• 12: K. Sugihara, M. Iri, Construction of the Voronoi diagram for one million generators in single precision arithmetic, First Canadian Conference on Computational Geometry, Montreal, Canada, 1989.

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Theory, Verification