Star splaying: an algorithm for repairing delaunay triangulations and convex hulls

ABSTRACT

Star splaying is a general-dimensional algorithm that takes as input a triangulation or an approximation of a convex hull, and produces the Delaunay triangulation, weighted Delaunay triangulation, or convex hull of the vertices in the input. If the input is "nearly Delaunay" or "nearly convex" in a certain sense quantified herein, and it is sparse (i.e. each input vertex adjoins only a constant number of edges), star splaying runs in time linear in the number of vertices. Thus, star splaying can be a fast first step in repairing a high-quality finite element mesh that has lost the Delaunay property after its vertices have moved in response to simulated physical forces. Star splaying is akin to Lawson's edge flip algorithm for converting a triangulation to a Delaunay triangulation, but it works in any dimensionality.

REFERENCES

• 1: Louis J. Billera, Paul Filliman, and Bernd Sturmfels. Constructions and Complexity of Secondary Polytopes. Advances in Mathematics 83(2):155--179, 1990.
• 2: Daniel K. Blandford, Guy E. Blelloch, David E. Cardoze, and Clemens Kadow. Compact Representations of Simplicial Meshes in Two and Three Dimensions. Twelfth International Meshing Roundtable, pages 135--146, September 2003.
• 3: Kevin Q. Brown. Voronoi Diagrams from Convex Hulls. Information Processing Letters 9:223--228, 1979.
• 4: 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]
• 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 [doi>10.1007/BF02187740]
• 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: Herbert Edelsbrunner. Geometry and Topology for Mesh Generation, Cambridge Monographs on Applied and Computational Mathematics, volume 6. Cambridge University Press, New York, 2001.
• 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 Nimish R. Shah. Incremental Topological Flipping Works for Regular Triangulations. Algorithmica 15(3):223--241, March 1996.
• 11: Izrail M. Gel'fand, Mikhail M. Kapranov, and Andrei V. Zelevinsky. Discriminants of Polynomials in Several Variables and Triangulations of Newton Polyhedra. Leningrad Mathematical Journal 2(3):449--505, 1991.
• 12: Ronald L. Graham. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1:132--133, 1972.
• 13: Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir. Randomized Incremental Construction of Delaunay and Voronoi Diagrams. Algorithmica 7(4):381--413, 1992.
• 14: Leonidas Guibas , Daniel Russel, An empirical comparison of techniques for updating Delaunay triangulations, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997846]
• 15: 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]
• 16: 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]
• 17: Michael Kallay. Convex Hull Algorithms in Higher Dimensions. Unpublished manuscript, Department of Mathematics, University of Oklahoma, Norman, Oklahoma, 1981.
• 18: Charles L. Lawson. Transforming Triangulations. Discrete Mathematics 3(4):365--372, 1972.
• 19: Software for C1 Surface Interpolation. Mathematical Software III (John R. Rice, editor), pages 161--194. Academic Press, New York, 1977.
• 20: 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]
• 21: Xiang-Yang Li , Shang-Hua Teng, Generating well-shaped Delaunay meshed in 3D, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 07-09, 2001, Washington, D.C., United States
• 22: Xiang-Yang Li, Shang-Hua Teng, and Alper Üngör. Simultaneous Refinement and Coarsening for Adaptive Meshing. Engineering with Computers 15(3):280--291, September 1999.
• 23: W. B. Raymond Lickorish. Simplicial Moves on Complexes and Manifolds. Proceedings of the Kirbyfest (Joel Hass and Martin Scharlemann, editors), Geometry & Topology Monographs, volume 2, pages 299--320. 1999.
• 24: Gary L. Miller , Dafna Talmor , Shang-Hua Teng, Optimal good-aspect-ratio coarsening for unstructured meshes, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.538-547, January 05-07, 1997, New Orleans, Louisiana, United States
• 25: Francisco Santos. A Point Configuration Whose Space of Triangulations is Disconnected. Journal of the American Mathematical Society 13(3):611--637, 2000.
• 26: Triangulations with Very Few Geometric Bistellar Neighbors. Discrete & Computational Geometry 23(1):15--33, January 2000.
• 27: Non-Connected Toric Hilbert Schemes. To appear in Mathematische Annalen, 2005.
• 28: E. Schönhardt. Über die Zerlegung von Drei-ecks-poly-edern in Tetraeder. Mathematische Annalen 98:309--312, 1928.
• 29: Raimund Seidel. Voronoi Diagrams in Higher Dimensions. Diplomarbeit, Institut für Informationsverarbeitung, Technische Universität Graz, 1982.
• 30: Raimund Seidel, Small-dimensional linear programming and convex hulls made easy, Discrete & Computational Geometry, v.6 n.5, p.423-434, 1991 [doi>10.1007/BF02574699]
• 31: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 32: 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]
• 33: Jonathan Richard Shewchuk, Updating and constructing constrained delaunay and constrained regular triangulations by flips, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777821]
• 34: Dafna Talmor. Well-Spaced Points for Numerical Methods. Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, August 1997. Available as Technical Report CMU-CS-97-164.

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:
Delaunay repair, Delaunay triangulation, convex hull, dynamic mesh generation, star flipping, star splaying