On deletion in Delaunay triangulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On deletion in Delaunay triangulations

Full text

Pdf (703 KB)

Source

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

Miami Beach, Florida, United States

Pages: 181 - 188

Year of Publication: 1999

ISBN:1-58113-068-6

Author

Olivier Devillers

INRIA, BP93, 06902 Sophia Antipolis, France

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

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/304893.304969 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.

	ADS97	R Alliez, O. Devillers, and J. Snoeyink. Removing degeneracies by perturbing the problem or the world. Research Report 3316, INRIA, 1997.
	AGSS89	A. Aggarwal , L. J. Guibas , J. Saxe , P. W. Shor, A linear-time algorithm for computing the Voronoi diagram of a convex polygon, Discrete & Computational Geometry, v.4 n.6, p.591-604, Sep. 1989 [doi>10.1007/BF02187749]
	Aur87	F Aurenhammer, Power diagrams: properties, algorithms and applications, SIAM Journal on Computing, v.16 n.1, p.78-96, Feb. 1987 [doi>10.1137/0216006]
	BBP98	Hervé Brönnimann , Christoph Burnikel , Sylvain Pion, Interval arithmetic yields efficient dynamic filters for computational geometry, Proceedings of the fourteenth annual symposium on Computational geometry, p.165-174, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276903]
	BD95	P. Bose and L. Devroye. Intersections with random geometric objects. Technical report, School of Computer Science, McGill University, 1995. Manuscript.
	BM71	H. Bruggesser and P. Mani. Shellable decompositions of cells and spheres. Math. Scand., 29:197-205, 1971.
	Che86	L. P Chew, Building Voronoi Diagrams for Convex Polygons in Linear Expected Time, Dartmouth College, Hanover, NH, 1990
	Dev98	Olivier Devillers, Improved incremental randomized Delaunay triangulation, Proceedings of the fourteenth annual symposium on Computational geometry, p.106-115, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276896]
	DLM98	L. Devroye, C. Lemaire, and J.-M. Moreau. Bin- Search & Walk, a fast point location procedure in 2d Delaunay triangulations, 1998. Submitted to this conference.
	DMT92	O. Devillers, S. Meiser, and M. Teillaud. The space of spheres, a geometric tool to unify duality results on Voronoi diagrams. In Proc. 4th Canad. Conf. Comput. Geom., pages 263-268, 1992.
	DP98	O. Devillers and E Preparata. A probabilistic analysis of the power of arithmetic filters. Discrete and Computational Geometry, 20:523- 547, 1998.
	DP99	O. Devillers and E Preparata. Further results on arithmetic filters for geometric predicates. In 15th European Workshop Comput. Geom., 1999.
	ES96	H. Edelsbrunner and N. R. Shah. Incremental topological flipping works for regular triangulations. Algorithmica, 15:223-241, 1996.
	GS78	P.J. Green and R. R. Sibson. Computing Dirichlet tessellations in the plane. Comput. J., 21:168- 173, 1978.
	Hel90	M. Heller. Triangulation algorithms for adaptive terrain modeling. In Proc. 4th Internat. Sympos. Spatial Data Handling, pages 163-174, 1990.
	Lem97	C. Lemaire. Triangulation de Delaunay et arbres multidimensionnels. Th#se de doctorat en sciences, l#cole des Mines de St-Etienne, France, 1997.
	Mid93	T. Midtb~. Spatial Modelling by Delaunay Networks of Two and Three Dimensions. Ph.D. thesis, Norvegian Institute of Technology, Trondheim, 1993.
	MSZ96	Ernst P. Mücke , Isaac Saias , Binhai Zhu, Fast randomized point location without preprocessing in two- and three-dimensional Delaunay triangulations, Proceedings of the twelfth annual symposium on Computational geometry, p.274-283, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237396]
	OBS92	Atsuyuki Okabe , Barry Boots , Kokichi Sugihara, Spatial tessellations: concepts and applications of Voronoi diagrams, John Wiley & Sons, Inc., New York, NY, 1992
	Ped70	D. Pedoe. Geometry, a comprehensive course. Dover Publications, New York, 1970.
	Sei86	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]
	Sei98	R. Seidel. The nature and meaning of perturbations in geometric computing. Discrete Comput. Geom., 19:1-17, 1998.
	Sno98	J. Snoeyink. Non redundant flip for point deletion in delaunay triangulation, 1998. Personnal communication.

CITED BY 3

	Jonathan Richard Shewchuk, Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations, Proceedings of the sixteenth annual symposium on Computational geometry, p.350-359, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Marc Vigo , Núria Pla , Josep Cotrina, Regular triangulations of dynamic sets of points, Computer Aided Geometric Design, v.19 n.2, p.127-149, February 2002
	Mir Abolfazl Mostafavi , Christopher Gold , Maciej Dakowicz, Delete and insert operations in Voronoi/Delaunay methods and applications, Computers & Geosciences, v.29 n.4, p.523-530, May 2003