Richard Shewchuk
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.
- Louis J. Billera, Paul Filliman, and Bernd Sturmfels. Constructions and Complexity of Secondary Polytopes. Advances in Mathematics 83(2):155--179, 1990.Google Scholar
Cross Ref
- 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.Google Scholar
- Kevin Q. Brown. Voronoi Diagrams from Convex Hulls. Information Processing Letters 9:223--228, 1979.Google ScholarCross Ref
- Siu-Wing Cheng, Tamal Krishna Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng. Sliver Exudation. Journal of the ACM 47(5):883--904, September 2000. Google ScholarDigital Library
- Kenneth L. Clarkson and Peter W. Shor. Applications of Random Sampling in Computational Geometry, II. Discrete & Computational Geometry 4(1):387--421, 1989.Google ScholarDigital Library
- 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.Google ScholarCross Ref
- Herbert Edelsbrunner. Geometry and Topology for Mesh Generation, Cambridge Monographs on Applied and Computational Mathematics, volume 6. Cambridge University Press, New York, 2001. Google ScholarDigital Library
- Herbert Edelsbrunner and Ernst Peter Mücke. Simulation of Simplicity: A Technique to Cope with Degenerate Cases in Geometric Algorithms. ACM Transactions on Graphics 9(1):66--104, 1990. Google ScholarDigital Library
- Herbert Edelsbrunner and Raimund Seidel. Voronoi Diagrams and Arrangements. Discrete & Computational Geometry 1:25--44, 1986. Google ScholarDigital Library
- Herbert Edelsbrunner and Nimish R. Shah. Incremental Topological Flipping Works for Regular Triangulations. Algorithmica 15(3):223--241, March 1996.Google Scholar
- 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.Google Scholar
- Ronald L. Graham. An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set. Information Processing Letters 1:132--133, 1972.Google ScholarCross Ref
- Leonidas J. Guibas, Donald E. Knuth, and Micha Sharir. Randomized Incremental Construction of Delaunay and Voronoi Diagrams. Algorithmica 7(4):381--413, 1992.Google ScholarDigital Library
- Leonidas J. Guibas and Daniel Russel. An Empirical Comparison of Techniques for Updating Delaunay Triangulations. Proceedings of the Twentieth Annual Symposium on Computational Geometry, pages 170--179, June 2004. Google ScholarDigital Library
- Barry Joe. Three-Dimensional Triangulations from Local Transformations. SIAM Journal on Scientific and Statistical Computing 10:718--741, 1989. Google ScholarDigital Library
- Construction of k-Dimensional Delaunay Triangulations Using Local Transformations. SIAM Journal on Scientific Computing 14(6):1415--1436, November 1993. Google ScholarDigital Library
- Michael Kallay. Convex Hull Algorithms in Higher Dimensions. Unpublished manuscript, Department of Mathematics, University of Oklahoma, Norman, Oklahoma, 1981.Google Scholar
- Charles L. Lawson. Transforming Triangulations. Discrete Mathematics 3(4):365--372, 1972.Google ScholarDigital Library
- Software for C1 Surface Interpolation. Mathematical Software III (John R. Rice, editor), pages 161--194. Academic Press, New York, 1977.Google Scholar
- Properties of n-Dimensional Triangulations. Computer Aided Geometric Design 3:231--246, 1986. Google ScholarDigital Library
- Xiang-Yang Li and Shang-Hua Teng. Generating Well-Shaped Delaunay Meshes in 3D. Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, pages 28--37, January 2001. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google Scholar
- Gary L. Miller, Dafna Talmor, and Shang-Hua Teng. Optimal Good-Aspect-Ratio Coarsening for Unstructured Meshes. Proceedings of the Eighth Annual Symposium on Discrete Algorithms, pages 538--547, January 1997. Google ScholarDigital Library
- Francisco Santos. A Point Configuration Whose Space of Triangulations is Disconnected. Journal of the American Mathematical Society 13(3):611--637, 2000.Google ScholarCross Ref
- Triangulations with Very Few Geometric Bistellar Neighbors. Discrete & Computational Geometry 23(1):15--33, January 2000.Google Scholar
- Non-Connected Toric Hilbert Schemes. To appear in Mathematische Annalen, 2005.Google Scholar
- E. Schönhardt. Über die Zerlegung von Drei-ecks-poly-edern in Tetraeder. Mathematische Annalen 98:309--312, 1928.Google ScholarCross Ref
- Raimund Seidel. Voronoi Diagrams in Higher Dimensions. Diplomarbeit, Institut für Informationsverarbeitung, Technische Universität Graz, 1982.Google Scholar
- Small-Dimensional Linear Programming and Convex Hulls Made Easy. Discrete & Computational Geometry 6(5):423--434, 1991. Google ScholarDigital Library
- Jonathan Richard Shewchuk. Tetrahedral Mesh Generation by Delaunay Refinement. Proceedings of the Fourteenth Annual Symposium on Computational Geometry, pages 86--95, June 1998. Google ScholarDigital Library
- Sweep Algorithms for Constructing Higher-Dimensional Constrained Delaunay Triangulations. Proceedings of the Sixteenth Annual Symposium on Computational Geometry, pages 350--359, June 2000. Google ScholarDigital Library
- Updating and Constructing Constrained Delaunay and Constrained Regular Triangulations by Flips. Proceedings of the Nineteenth Annual Symposium on Computational Geometry, pages 181--190, June 2003. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- Star splaying: an algorithm for repairing delaunay triangulations and convex hulls
Recommendations
A GPU accelerated algorithm for 3D Delaunay triangulation
I3D '14: Proceedings of the 18th meeting of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and GamesWe propose the first algorithm to compute the 3D Delaunay triangulation (DT) on the GPU. Our algorithm uses massively parallel point insertion followed by bilateral flipping, a powerful local operation in computational geometry. Although a flipping ...
Efficient parallel geometric algorithms on a mesh of trees
ACM-SE 33: Proceedings of the 33rd annual on Southeast regional conferenceIn this paper, we present some efficient parallel geometric algorithms for computing the All Nearest Neighbors, Delaunay Triangulation, Convex Hull, and Voronoi Diagram of a point set S with N points in the plane. The algorithm of All Nearest Neighbors ...
Comments