Perturbations and vertex removal in a 3D delaunay triangulation

ABSTRACT

Though Delaunay triangulations are very well known geometric data structures, the problem of the robust removal of a vertex in a three-dimensional Delaunay triangulation is still a problem in practice.We propose a simple method that allows to remove any vertex even when the points are in very degenerate configurations. The solution is available in CGAL.

REFERENCES

• 1: 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
• 2: Pierre Alliez, Olivier Devillers, and Jack Snoeyink. Removing degeneracies by perturbing the problem or the world. Reliable Computing, 6:61--79, 2000. Special Issue on Computational Geometry, to appear.
• 3: Siu-Wing Cheng , Tamal K. Dey, Quality meshing with weighted Delaunay refinement, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.137-146, January 06-08, 2002, San Francisco, California
• 4: Siu-Wing Cheng , Tamal K. Dey , Herbert Edelsbrunner , Michael A. Facello , Shang-Hua Teng, Sliver exudation, Proceedings of the fifteenth annual symposium on Computational geometry, p.1-13, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304894]
• 5: L. P Chew, Building Voronoi Diagrams for Convex Polygons in Linear Expected Time, Dartmouth College, Hanover, NH, 1990
• 6: Olivier Devillers. On deletion in Delaunay triangulation. Internat. J. Comput. Geom. Appl., 12:193--205, 2002.
• 7: Olivier Devillers, Stefan Meiser, and Monique Teillaud. The space of spheres, a geometric tool to unify dual-ity results on Voronoi diagrams. In Proc. 4th Canad. Conf. Comput. Geom., pages 263--268, 1992. Techni-cal Report INRIA 1620, http://www.inria.fr/rrrt/rr-1620.html.
• 8: Tamal K. Dey , Joachim Giesen, Detecting undersampling in surface reconstruction, Proceedings of the seventeenth annual symposium on Computational geometry, p.257-263, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378682]
• 9: M. B. Dillencourt, Realizability of Delaunay triangulations, Information Processing Letters, v.33 n.6, p.283-287, February 1990 [doi>10.1016/0020-0190(90)90210-O ]
• 10: 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]
• 11: Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
• 12: Stefan Funke , Kurt Mehlhorn, Look — a Lazy Object-Oriented Kernel for geometric computation, Proceedings of the sixteenth annual symposium on Computational geometry, p.156-165, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336196]
• 13: M. Heller. Triangulation algorithms for adaptive terrain modeling. In Proe. 4th Internat. Sympos. Spatial Data Handling, pages 163--174, 1990.
• 14: F. Hurtado, M. Noy, and J. Urrutia. Flipping edges in triangulations. Discrete Comput. Geom., 22(3):333--346, 1999.
• 15: Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
• 16: R. Seidel. The nature and meaning of perturbations in geometric computing. Discrete Comput. Geom., 19:1--17, 1998.

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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

General Terms:
Algorithms, Theory