Optimality of the Delaunay triangulation in Rd

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimality of the Delaunay triangulation in R^d

Full text

Pdf (611 KB)

Source

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

North Conway, New Hampshire, United States

Pages: 357 - 363

Year of Publication: 1991

ISBN:0-89791-426-0

Author

V. T. Rajan

Manufacturing Research Department, IBM Research Division, T J Watson Research Center, NY

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): 3, Downloads (12 Months): 34, Citation Count: 9

Additional Information:

references cited by index terms collaborative colleagues

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/109648.109688 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	Aurenhammer F., Voronoi diagrams- survey, Inst. for Inf. Proc., Graz Tech. Univ. report, (1988).
	2	Brown K.Q., Voronoi diagrams from convex hulls, Inform. Process. Lett., 9(1970) 223-228.
	3	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	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	H. Edelsbrunner, An acyclicity theorem for cell complexes in d dimensions, Proceedings of the fifth annual symposium on Computational geometry, p.145-151, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73850]
	6	Edelsbrunner, H. Private communication.
	7	Fortune, S. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2(2) (1987), 153-174.
	8	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	9	Lawson, C.L. Generation of a triangular grid with applications to contour plotting. Memo 299, Calif. Inst. Jet Propul. Lab. (1972).
	10	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	11	Shamos, M.I., and Hoey, D. Closest-point problems. In Proc.16th Ann. IEEE Sympos. Found. Comput. Sci. (1975), 151-162. New Haven, Conn., (1978)
	12	Michael Ian Shamos, Computational geometry., 1978
	13	Srinivasan V., Nackm~n L.R., Tang, J. and Meshkat $.N., Automatic Mesh Generation using the Symmetric Axis Transformation of Polygonal Domains, IBM RC 16132, (1990).

CITED BY 9

	Michela Bertolotto , Leila De Floriani , Paola Marzano, Pyramidal simplicial complexes, Proceedings of the third ACM symposium on Solid modeling and applications, p.153-162, May 17-19, 1995, Salt Lake City, Utah, United States
	Marshall Bern , Paul Chew , David Eppstein , Jim Ruppert, Dihedral bounds for mesh generation in high dimensions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.189-196, January 22-24, 1995, San Francisco, California, United States
	H. Edelsbrunner , N. R. Shah, Incremental topological flipping works for regular triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.43-52, June 10-12, 1992, Berlin, Germany
	Herbert Edelsbrunner , Tiow Seng Tan, An upper bound for conforming Delaunay triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.53-62, June 10-12, 1992, Berlin, Germany
	Oleg R. Musin, Properties of the Delaunay triangulation, Proceedings of the thirteenth annual symposium on Computational geometry, p.424-426, June 04-06, 1997, Nice, France
	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991
	Lusine Yepremyan , James E. Falk, Delaunay partitions in Rⁿ applied to non-convex programs and vertex/facet enumeration problems, Computers and Operations Research, v.32 n.4, p.793-812, April 2005
	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
	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