Updating and constructing constrained delaunay and constrained regular triangulations by flips

ABSTRACT

I discuss algorithms based on bistellar flips for inserting and deleting constraining (d - 1)-facets in d-dimensional constrained Delaunay triangulations (CDTs) and weighted CDTs, also known as constrained regular triangulations. The facet insertion algorithm is likely to outperform other known algorithms on most inputs. The facet deletion algorithm is the first proposed for d > 2, short of recomputing the CDT from scratch. An incremental facet insertion algorithm that begins with an unconstrained Delaunay triangulation can construct the CDT of a ridge-protected piecewise linear complex with n_v vertices in O(n_v^{[d / 2] + 1} log n_v) time. Hence, in odd dimensions, CDT construction by incremental facet insertion is within a factor of log n_v of worst-case optimal. Perhaps the most important feature of these algorithms is that they are relatively easy to implement.

REFERENCES

• 1: Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. Pseudo-Triangulations from Surfaces and a Novel Type of Edge Flip. Manuscript, 2003.
• 2: Siu-Wing Cheng , Tamal K. Dey , Herbert Edelsbrunner , Michael A. Facello , Shang-Hua Teng, Silver exudation, Journal of the ACM (JACM), v.47 n.5, p.883-904, Sept. 2000 [doi>10.1145/355483.355487]
• 3: L.Paul Chew. Constrained Delaunay Triangulations. Algorithmica 4(1):97--108, 1989.
• 4: ______.Guaranteed-Quality Triangular Meshes. Technical Report TR-89-983, Department of Computer Science, Cornell University, 1989.
• 5: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989
• 6: Jesús A. de Loera, Francisco Santos, and Jorge Urrutia. The Number of Geometric Bistellar Neighbors of a Triangulation. Discrete & Computational Geometry 21(1):131--142, 1999.
• 7: Boris N. Delaunay. Sur la Sphère Vide. Izvestia Akademia Nauk SSSR, VII Seria, Otdelenie Matematicheskii i Estestvennyka Nauk 7:793--800, 1934.
• 8: 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]
• 9: Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
• 10: Herbert Edelsbrunner and N. R. Shah. Incremental Topological Flipping Works for Regular Triangulations. Algorithmica 15(3):223--241, March 1996.
• 11: Leonidas J. Guibas, Kinetic data structures: a state of the art report, Proceedings of the third workshop on the algorithmic foundations of robotics on Robotics : the algorithmic perspective: the algorithmic perspective, p.191-209, August 1998, Houston, Texas, United States
• 12: Barry Joe, Three-dimensional triangulations from local transformations, SIAM Journal on Scientific and Statistical Computing, v.10 n.4, p.718-741, July 1989 [doi>10.1137/0910044]
• 13: Barry Joe, Construction of K-dimensional Delaunay triangulations using local transformations, SIAM Journal on Scientific Computing, v.14 n.6, p.1415-1436, Nov. 1993 [doi>10.1137/0914083]
• 14: Charles L. Lawson. Software for C1 Surface Interpolation. Mathematical Software III (John~R. Rice, editor), pages 161--194. Academic Press, New York, 1977.
• 15: Charles L. Lawson, Properties of n-dimensional triangulations, Computer Aided Geometric Design, v.3 n.4, p.231-246, 1987 [doi>10.1016/0167-8396(86)90001-4]
• 16: Der-Tsai Lee and A. K. Lin. Generalized Delaunay Triangulations for Planar Graphs. Discrete & Computational Geometry 1:201--217, 1986.
• 17: Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington, and Han Wang. Control Volume Meshes using Sphere Packing: Generation, Refinement and Coarsening. Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania), pages 47--61, October 1996.
• 18: Johann Radon. Mengen Konvexer Korper, die Einen Gemeinschaftlichen Punkt Enthalten. Mathematische Annalen 83:113--115, 1921.
• 19: Raimund Seidel, The upper bound theorem for polytopes: an easy proof of its asymptotic version, Computational Geometry: Theory and Applications, v.5 n.2, p.115-116, Sept. 1995 [doi>10.1016/0925-7721(95)00013-Y ]
• 20: ______.Constrained Delaunay Triangulations and Voronoi Diagrams with Obstacles. 1978--1988 Ten Years IIG (H. S. Poingratz and W. Schinnerl, editors), pages 178--191. Institute for Information Processing, Graz University of Technology, 1988.
• 21: Jonathan Richard Shewchuk, A condition guaranteeing the existence of higher-dimensional constrained Delaunay triangulations, Proceedings of the fourteenth annual symposium on Computational geometry, p.76-85, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276893]
• 22: Jonathan Richard Shewchuk, Mesh generation for domains with small angles, Proceedings of the sixteenth annual symposium on Computational geometry, p.1-10, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336163]
• 23: Jonathan Richard Shewchuk, Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations, Proceedings of the sixteenth annual symposium on Computational geometry, p.350-359, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336222]
• 24: ______.Constrained Delaunay Tetrahedralizations and Provably Good Boundary Recovery. Eleventh International Meshing Roundtable (Ithaca, New York), pages 193--204. Sandia National Laboratories, September 2002.
• 25: ______.What is a Good Linear Element? Interpolation, Conditioning, and Quality Measures. Eleventh International Meshing Roundtable (Ithaca, New York), pages 115--126. Sandia National Laboratories, September 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
bistellar flip, constrained delaunay triangulation