Improved incremental randomized Delaunay triangulation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Improved incremental randomized Delaunay triangulation

Full text

Pdf (932 KB)

Source

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

Minneapolis, Minnesota, United States

Pages: 106 - 115

Year of Publication: 1998

ISBN:0-89791-973-4

Author

Olivier Devillers

INRIA, BP93, 06902 Sophia Antipolis

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): 61, Citation Count: 12

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

	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]
	BD95	P. Bose and L. Devroye. Intersections with random geometric objects. Technical report, School of Computer Science, McGill University, 1995. Manuscript.
	BDH93	C.B. Barber, D. P. Dobkin, and H. Huhdanpaa. The Quickhull algorithm for convex hull. Technical Report GCG53, Geometry Center, Univ. of Minnesota, July 1993.
	BT86	J D Boissonnat , M Teillaud, The hierarchical representation of objects: the Delaunay tree, Proceedings of the second annual symposium on Computational geometry, p.260-268, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10543]
	BT93	Jean-Daniel Boissonnat , Monique Teillaud, On the randomized construction of the Delaunay tree, Theoretical Computer Science, v.112 n.2, p.339-354, May 10, 1993 [doi>10.1016/0304-3975(93)90024-N]
	Che86	L. P Chew, Building Voronoi Diagrams for Convex Polygons in Linear Expected Time, Dartmouth College, Hanover, NH, 1990
	Che87	L. P. Chew, Constrained Delaunay triangulations, Proceedings of the third annual symposium on Computational geometry, p.215-222, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41981]
	DMT92	Olivier Devillers , Stefan Meiser , Monique Teillaud, Fully dynamic Delaunay triangulation in logarithmic expected time per operation, Computational Geometry: Theory and Applications, v.2 n.2, p.55-80, Oct. 1992 [doi>10.1016/0925-7721(92)90025-N]
	GKS92	L, J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algoritlunica, 7:381--413, 1992.
	Law77	C. L, Lawson. Software for U1 surface interpolation. In J. R. Rice, editor, Math. Software iii, pages 161-194. Academic Press, New York, NY, 1977.
	MR95	Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
	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]
	Mul91	Ketan Mulmuley, Randomized multidimensional search trees (extended abstract): dynamic sampling, Proceedings of the seventh annual symposium on Computational geometry, p.121-131, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109662]
	Mul94	K. Mulmuley. Computational Geometry: An Introductlon Through Randomized Algorithms. Prentice Hall, Englewood Cliffs, NJ, 1994.
	PY92	Mike Paterson , F. Frances Yao, On Nearest-Neighbor Graphs, Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.416-426, July 13-17, 1992
	SD97	Peter Su , Robert L. Scot Drysdale, A comparison of sequential Delaunay triangulation algorithms, Computational Geometry: Theory and Applications, v.7 n.5-6, p.361-385, April 1997 [doi>10.1016/S0925-7721(96)00025-9]
	She96	Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.203-222, May 27-28, 1996
	TLP96	Roberto Tamassia , Giuseppe Liotta , Franco P. Preparata, Robust Proximity Queries in Implicit Voronoi Diagrams, Proceedings of the 8th Canadian Conference on Computational Geometry, p.1-1, August 12-15, 1996

CITED BY 12

	Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Sunghee Choi , Nina Amenta, Delaunay triangulation programs on surface data, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.135-136, January 06-08, 2002, San Francisco, California
	Olivier Devillers , Sylvain Pion , Monique Teillaud, Walking in a triangulation, Proceedings of the seventeenth annual symposium on Computational geometry, p.106-114, June 2001, Medford, Massachusetts, United States
	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
	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
	Josef Kohout , Ivana Kolingerová, Parallel Delaunay triangulation based on circum-circle criterion, Proceedings of the 19th spring conference on Computer graphics, April 24-26, 2003, Budmerice, Slovakia
	Jean-Daniel Boissonnat , Olivier Devillers , Monique Teillaud , Mariette Yvinec, Triangulations in CGAL (extended abstract), Proceedings of the sixteenth annual symposium on Computational geometry, p.11-18, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Leonidas Guibas , Daniel Russel, An empirical comparison of techniques for updating Delaunay triangulations, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Tamy Boubekeur , Patrick Reuter , Christophe Schlick, Surfel Stripping, Proceedings of the 3rd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, November 29-December 02, 2005, Dunedin, New Zealand
	Chun-Hsien Wu , Kuo-Chuan Lee , Yeh-Ching Chung, A Delaunay Triangulation based method for wireless sensor network deployment, Computer Communications, v.30 n.14-15, p.2744-2752, October, 2007
	E. S. Petrov , T. M. Yakhno, Subdefinite Models and Logic Programming: Implementation of Constraints, Programming and Computing Software, v.27 n.2, p.95-100, March-April 2001
	Chuan-Chu Kuo , Hong-Tzong Yau, A New Combinatorial Approach to Surface Reconstruction with Sharp Features, IEEE Transactions on Visualization and Computer Graphics, v.12 n.1, p.73-82, January 2006