More Web Proxy on the site http://driver.im/

Article

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

Author:

Richard ShewchukAuthors Info & Claims

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

Pages 237 - 246

https://doi.org/10.1145/1064092.1064129

Published: 06 June 2005 Publication History

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 Krishna Dey, Herbert Edelsbrunner, Michael A. Facello, and Shang-Hua Teng. Sliver Exudation. Journal of the ACM 47(5):883--904, September 2000.

Digital Library

[5]

Kenneth L. Clarkson and Peter W. Shor. Applications of Random Sampling in Computational Geometry, II. Discrete & Computational Geometry 4(1):387--421, 1989.

Digital Library

[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.

Digital Library

[8]

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.

Digital Library

[9]

Herbert Edelsbrunner and Raimund Seidel. Voronoi Diagrams and Arrangements. Discrete & Computational Geometry 1:25--44, 1986.

Digital Library

[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.

Digital Library

[14]

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.

Digital Library

[15]

Barry Joe. Three-Dimensional Triangulations from Local Transformations. SIAM Journal on Scientific and Statistical Computing 10:718--741, 1989.

Digital Library

[16]

Construction of k-Dimensional Delaunay Triangulations Using Local Transformations. SIAM Journal on Scientific Computing 14(6):1415--1436, November 1993.

Digital Library

[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.

Digital Library

[19]

Software for C1 Surface Interpolation. Mathematical Software III (John R. Rice, editor), pages 161--194. Academic Press, New York, 1977.

[20]

Properties of n-Dimensional Triangulations. Computer Aided Geometric Design 3:231--246, 1986.

Digital Library

[21]

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.

Digital Library

[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, 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.

Digital Library

[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]

Small-Dimensional Linear Programming and Convex Hulls Made Easy. Discrete & Computational Geometry 6(5):423--434, 1991.

Digital Library

[31]

Jonathan Richard Shewchuk. Tetrahedral Mesh Generation by Delaunay Refinement. Proceedings of the Fourteenth Annual Symposium on Computational Geometry, pages 86--95, June 1998.

Digital Library

[32]

Sweep Algorithms for Constructing Higher-Dimensional Constrained Delaunay Triangulations. Proceedings of the Sixteenth Annual Symposium on Computational Geometry, pages 350--359, June 2000.

Digital Library

[33]

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.

Digital Library

[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.

Cited By

Schwab ALunze J(2023)Formation Control Over Delaunay Triangulation Networks With Guaranteed Collision AvoidanceIEEE Transactions on Control of Network Systems10.1109/TCNS.2022.320335110:1(419-429)Online publication date: Mar-2023
https://doi.org/10.1109/TCNS.2022.3203351
Caraffa LMemari PYirci MBredif M(2019)Tile & Merge: Distributed Delaunay Triangulations for Cloud Computing2019 IEEE International Conference on Big Data (Big Data)10.1109/BigData47090.2019.9006534(1613-1618)Online publication date: Dec-2019
https://doi.org/10.1109/BigData47090.2019.9006534
Qi MYan KZheng Y(2019)GPredicates: GPU Implementation of Robust and Adaptive Floating-Point Predicates for Computational GeometryIEEE Access10.1109/ACCESS.2019.29116417(60868-60876)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2911641
Show More Cited By

Index Terms

Star splaying: an algorithm for repairing delaunay triangulations and convex hulls
1. Theory of computation
  1. Design and analysis of algorithms

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 Games

We 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
ACMSE '95: Proceedings of the 33rd annual ACM Southeast Conference

In 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 ...
Fast topological construction of Delaunay triangulations and Voronoi diagrams

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

June 2005

398 pages

ISBN:1581139918

DOI:10.1145/1064092

Program Chairs:
Joe Mitchell
SUNY Stony Brook
,
Günter Rote
Freie Universität Berlin

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG05

Sponsor:

SoCG05: The 21st Annual ACM Symposium on Computational Geometry 2005

June 6 - 8, 2005

Pisa, Italy

Acceptance Rates

SCG '05 Paper Acceptance Rate 41 of 141 submissions, 29%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

44
Total Citations
View Citations
1,156
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Schwab ALunze J(2023)Formation Control Over Delaunay Triangulation Networks With Guaranteed Collision AvoidanceIEEE Transactions on Control of Network Systems10.1109/TCNS.2022.320335110:1(419-429)Online publication date: Mar-2023
https://doi.org/10.1109/TCNS.2022.3203351
Caraffa LMemari PYirci MBredif M(2019)Tile & Merge: Distributed Delaunay Triangulations for Cloud Computing2019 IEEE International Conference on Big Data (Big Data)10.1109/BigData47090.2019.9006534(1613-1618)Online publication date: Dec-2019
https://doi.org/10.1109/BigData47090.2019.9006534
Qi MYan KZheng Y(2019)GPredicates: GPU Implementation of Robust and Adaptive Floating-Point Predicates for Computational GeometryIEEE Access10.1109/ACCESS.2019.29116417(60868-60876)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2911641
Boissonnat JChazal FYvinec M(2018)IndexGeometric and Topological Inference10.1017/9781108297806.014(231-234)Online publication date: 14-Sep-2018
https://doi.org/10.1017/9781108297806.014
Boissonnat JChazal FYvinec M(2018)BibliographyGeometric and Topological Inference10.1017/9781108297806.013(224-230)Online publication date: 14-Sep-2018
https://doi.org/10.1017/9781108297806.013
Boissonnat JChazal FYvinec M(2018)Homology InferenceGeometric and Topological Inference10.1017/9781108297806.012(197-223)Online publication date: 14-Sep-2018
https://doi.org/10.1017/9781108297806.012
Boissonnat JChazal FYvinec M(2018)Distance to Probability MeasuresGeometric and Topological Inference10.1017/9781108297806.011(180-196)Online publication date: 14-Sep-2018
https://doi.org/10.1017/9781108297806.011
Boissonnat JChazal FYvinec M(2018)Stability of Distance FunctionsGeometric and Topological Inference10.1017/9781108297806.010(163-179)Online publication date: 14-Sep-2018
https://doi.org/10.1017/9781108297806.010
Boissonnat JChazal FYvinec M(2018)Reconstruction of SubmanifoldsGeometric and Topological Inference10.1017/9781108297806.009(137-160)Online publication date: 14-Sep-2018
https://doi.org/10.1017/9781108297806.009
Boissonnat JChazal FYvinec M(2018)Triangulation of SubmanifoldsGeometric and Topological Inference10.1017/9781108297806.008(115-136)Online publication date: 14-Sep-2018
https://doi.org/10.1017/9781108297806.008
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents