Sink-insertion for mesh improvement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sink-insertion for mesh improvement

Full text

Pdf (1.29 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the seventeenth annual symposium on Computational geometry table of contents

Medford, Massachusetts, United States

Pages: 115 - 123

Year of Publication: 2001

ISBN:1-58113-357-X

Authors

Herbert Edelsbrunner	Department of Computer Science, Duke University, Durham, NC 27708, Raindrop Geomagic, RTP, NC
Damrong Guoy	Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 12, Citation Count: 6

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/378583.378644 What is a DOI?

ABSTRACT

We propose sink-insertion as a new technique to improve the mesh quali ty of Delaunay triangulations. We compare it with the conventional circumcenter-insertion technique under three scheduling regimes: incremental, in blocks, and in parallel. Justification for sink-insertion is given in terms of mesh quality, numerical robustness, running time, and ease of parallelization.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	P. S. Alexandrov. Combinatorial Topology, Volumes 1, 2 and 3. Dover, Mineola, New York, 1998.
	2	L. P. Chew. Guaranteed-quality triangular meshes. Report TR 89-983, Comput. Sci. Dept., Cornell Univ., Ithaca, New York, 1989.
	3	B. Delaunay. Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7 (1934), 793-800.
	4	T. K. Dey, C. Bajaj and K. Sugihara. On good triangulations in three dimensions. Internat. J. Comput. Geom. Appl. 2 (1992), 75-95.
	5	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]
	6	Herbert Edelsbrunner , Michael Facello , Jie Liang, On the definition and the construction of pockets in macromolecules, Discrete Applied Mathematics, v.88 n.1-3, p.83-102, Nov. 9, 1998 [doi>10.1016/S0166-218X(98)00067-5]
	7	Jim Ruppert, A Delaunay refinement algorithm for quality 2-dimensional mesh generation, Journal of Algorithms, v.18 n.3, p.548-585, May 1995
	8	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]
	9	D. F. Watson. Computing the n-dimensional Delaunay tessellation with applications to Voronoi polytopes. Computer Journal 24 (1981), 167-172.

CITED BY 6

	Daniel A. Spielman , Shang-Hua Teng , Alper Üngör, Time complexity of practical parallel steiner point insertion algorithms, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Alper Üngör, Off-centers: A new type of Steiner points for computing size-optimal quality-guaranteed Delaunay triangulations, Computational Geometry: Theory and Applications, v.42 n.2, p.109-118, February, 2009
	Sariel Har-Peled , Alper Üngör, A time-optimal delaunay refinement algorithm in two dimensions, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Hale Erten , Alper Üngör, Triangulations with locally optimal Steiner points, Proceedings of the fifth Eurographics symposium on Geometry processing, July 04-06, 2007, Barcelona, Spain
	Alla Sheffer , Alper Üngör, Efficient adaptive meshing of parametric models, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.59-70, May 2001, Ann Arbor, Michigan, United States
	Andrey N. Chernikov , Nikos P. Chrisochoides, Practical and efficient point insertion scheduling method for parallel guaranteed quality delaunay refinement, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France