Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations

Full text

Pdf (1.16 MB)

Source

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

Clear Water Bay, Kowloon, Hong Kong

Pages: 350 - 359

Year of Publication: 2000

ISBN:1-58113-224-7

Author

Jonathan Richard Shewchuk

Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, California

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): 5, Downloads (12 Months): 35, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/336154.336222 What is a DOI?

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	L. Paul Chew. Constrained Delaunay Triangulations. Algorithmica 4(1):97-108, 1989.
	2	Olivier Devillers, On deletion in Delaunay triangulations, Proceedings of the fifteenth annual symposium on Computational geometry, p.181-188, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304969]
	3	Rex A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Discrete & Computational Geometry, v.6 n.4, p.343-367, 1991
	4	Herbert Edelsbrunner , Raimund Seidel, Voronoi diagrams and arrangements, Discrete & Computational Geometry, v.1 n.1, p.25-44, 1986 [doi>10.1007/BF02187681]
	5	Steven Fortune. ,4 Sweepline Algorithm for Voronoi Diagrams. Algorithmica 2(2): 153-174, 1987.
	6	D.-T. Lee and A. K. Lin. Generalized Delaunay Triangulations for Planar Graphs. Discrete & Computational Geometry 1:20 I-217, 1986.
	7	Gary L. Miller, Dafna Talmor, Shang-Hua Teng, Noel Walkington, and Han Wang. Control Volume Meshes Using Sphere Pacla'ng: Generation, Refinement and Coarsening. Fifth International Meshing Roundtable (Pittsburgh, Pennsylvania), pages 47-61, October 1996.
	8	Jim Ruppert , Raimund Seidel, On the difficulty of triangulating three-dimensional nonconvex polyhedra., Discrete & Computational Geometry, v.7 n.3, p.227-253, 1992
	9	E. SchiSnhardt. Uber die Zerlegung von Dreieckspolyedern in Tetraeder. Mathematische Annalen 98:309-312, 1928.
	10	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
	11	Jonathan Richard Shewchuk. Delaunay Refinement Mesh Generation. Ph.D. thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania, May 1997. Available as Technical Report CMU-CS-97-137.
	12	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]
	13	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]
	14	M. Tanemura, T. Ogawa, and N. Ogita. A New Algorithm for Three-Dimensional Voronoi Tessellation. Journal of Computational Physics 51:191-207, 1983.

CITED BY 4

	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
	Richard Shewchuk, Star splaying: an algorithm for repairing delaunay triangulations and convex hulls, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Boting Yang , Cao An Wang, Detecting tetrahedralizations of a set of line segments, Journal of Algorithms, v.53 n.1, p.1-35, October 2004
	George Biros , Lexing Ying , Denis Zorin, A fast solver for the Stokes equations with distributed forces in complex geometries, Journal of Computational Physics, v.193 n.1, p.317-348, January 2004