Nice point sets can have nasty Delaunay triangulations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Nice point sets can have nasty Delaunay triangulations

Full text

Pdf (439 KB)

Source

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

Medford, Massachusetts, United States

Pages: 96 - 105

Year of Publication: 2001

ISBN:1-58113-357-X

Author

Jeff Erickson

University of Illinois, Urbana-Champaign

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): 8, Downloads (12 Months): 44, Citation Count: 18

Additional Information:

abstract 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/378583.378636 What is a DOI?

ABSTRACT

We consider the complexity of Delaunay triangulations of sets of point s in $\Real^3$ under certain practical geometric constraints. The \emph{spread} of a set of points is the ratio between the longest and shortest pairwise distances. We show that in the worst case, the Delaunay triangulation of $n$ points in~$\Real^3$ with spread $\Delta$ has complexity $\Omega(\min\set{\Delta^3, n\Delta, n^2})$ and $O(\min\set{\Delta^4, n^2})$. For the case $\Delta = \Theta(\sqrt{n})$, our lower bound construction consists of a uniform sample of a smooth convex surface with bounded curvature. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.

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	N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22(4):481-504, 1999.
	2	Nina Amenta , Marshall Bern , David Eppstein, The crust and the &Bgr;-Skeleton: combinatorial curve reconstruction, Graphical Models and Image Processing, v.60 n.2, p.125-135, March 1, 1998 [doi>10.1006/gmip.1998.0465]
	3	Nina Amenta , Marshall Bern , Manolis Kamvysselis, A new Voronoi-based surface reconstruction algorithm, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.415-421, July 1998 [doi>10.1145/280814.280947]
	4	N. Amenta , S. Choi , T. K. Dey , N. Leekha, A simple algorithm for homeomorphic surface reconstruction, Proceedings of the sixteenth annual symposium on Computational geometry, p.213-222, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336207]
	5	N. Amenta, S. Choi, and R. Kolluri. The power crust, unions of balls, and the medial axis transform. To appear in Internat. J. Comput. Geom. Appl.h http://www.cs.utexas.edu/users/ amenta/pubs/power.ps.gz i .
	6	D. Attali, r-regular shape reconstruction from unorganized points, Computational Geometry: Theory and Applications, v.10 n.4, p.239-247, July 1, 1998 [doi>10.1016/S0925-7721(98)00013-3]
	7	Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995 [doi>10.1145/218380.218424]
	8	Mark de Berg , Matthew Katz , A. Frank van der Stappen , Jules Vleugels, Realistic input models for geometric algorithms, Proceedings of the thirteenth annual symposium on Computational geometry, p.294-303, June 04-06, 1997, Nice, France [doi>10.1145/262839.262986]
	9	F. Bernardini and C. L. Bajaj. Sampling and reconstructing manifolds using alpha-shapes. Proc. 9th Canad. Conf. Comput. Geom., 193-198. 1997.
	10	Marshall Bern , David Eppstein , John Gilbert, Provably good mesh generation, Journal of Computer and System Sciences, v.48 n.3, p.384-409, June 1994 [doi>10.1016/S0022-0000(05)80059-5]
	11	J.-D. Boissonnat. Representing 2d and 3d shapes with the Delaunay triangulation. Proc. 7th IEEE Internat. Conf. Pattern Recogn., 745-748, 1984.
	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 [doi>10.1145/336154.336208]
	13	Paul B. Callahan , S. Rao Kosaraju, A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, Journal of the ACM (JACM), v.42 n.1, p.67-90, Jan. 1995 [doi>10.1145/200836.200853]
	14	Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , John E. Hershberger , Raimund Seidel , Micha Sharir, Selecting Heavily Covered Points, SIAM Journal on Computing, v.23 n.6, p.1138-1151, Dec. 1994 [doi>10.1137/S0097539790179919]
	15	Ho-Lun Cheng , Tamal K. Dey , Herbert Edelsbrunner , John Sullivan, Dynamic skin triangulation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.47-56, January 07-09, 2001, Washington, D.C., United States
	16	Siu-Wing Cheng , Tamal K. Dey , Herbert Edelsbrunner , Michael A. Facello , Shang-Hua Teng, Sliver exudation, Proceedings of the fifteenth annual symposium on Computational geometry, p.1-13, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304894]
	17	K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete Comput. Geom. 22:63-93, 1999.
	18	T. K. Dey, S. Funke, and E. Ramos. Surface reconstruction in almost linear time under locally uniform sampling. Unpublished manuscript, 2001.
	19	R. Dwyer. The expected number of k-faces of a Voronoi diagram. Internat. J. Comput. Math. 26(5):13-21, 1993.
	20	Rex A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Discrete & Computational Geometry, v.6 n.4, p.343-367, 1991 [doi>10.1007/BF02574694]
	21	Herbert Edelsbrunner , Xiang-Yang Li , Gary Miller , Andreas Stathopoulos , Dafna Talmor , Shang-Hua Teng , Alper Üngör , Noel Walkington, Smoothing and cleaning up slivers, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.273-277, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335338]
	22	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
	23	Christopher Gold, Crust and anti-crust: a one-step boundary and skeleton extraction algorithm, Proceedings of the fifteenth annual symposium on Computational geometry, p.189-196, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304971]
	24	M. Golin and H. Na. On the average complexity of 3d-Voronoi diagrams of random points on convex polytopes. Proc. 12th Canadian Conf. Comput. Geom., 127-135, 2000. (http://www.cs.unb.ca/ conf/cccg/eProceedings/44.ps.ga).
	25	B. Guo, J. Menon, and B. Willette. Surface reconstruction using alpha shapes. Comput. Graph. Forum 16(4):177-190, 1997.
	26	Hisamoto Hiyoshi , Kokichi Sugihara, Voronoi-based interpolation with higher continuity, Proceedings of the sixteenth annual symposium on Computational geometry, p.242-250, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336210]
	27	X.-Y. Li and S.-H. Teng. Generating sliver-free three dimensional meshes. Proc. 12th Annu. ACM- SIAM Sympos. Discrete Algorithms, 2001.
	28	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]
	29	J. Vleugels. On Fatness and Fitness: Realistic Input Models for Geometric Algorithms. Ph.D. Thesis, Dept. Comput. Sci., Univ. Utrecht, 1997.

CITED BY 18

	Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Proceedings of the eighteenth annual symposium on Computational geometry, p.33-42, June 05-07, 2002, Barcelona, Spain
	Stefan Funke , Edgar A. Ramos, Smooth-surface reconstruction in near-linear time, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.781-790, January 06-08, 2002, San Francisco, California
	Jeff Erickson, Dense point sets have sparse Delaunay triangulations: or "…but not too nasty", Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.125-134, January 06-08, 2002, San Francisco, California
	Mordecai J. Golin , Hyeon-Suk Na, The probabilistic complexity of the Voronoi diagram of points on a polyhedron, Proceedings of the eighteenth annual symposium on Computational geometry, p.209-216, June 05-07, 2002, Barcelona, Spain
	Mordecai J. Golin , Hyeon-Suk Na, On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes, Computational Geometry: Theory and Applications, v.25 n.3, p.197-231, July 2003
	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
	Dominique Attali , Jean-Daniel Boissonnat, A linear bound on the complexity of the delaunay triangulation of points on polyhedral surfaces, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Dominique Attali , Jean-Daniel Boissonnat , André Lieutier, Complexity of the delaunay triangulation of points on surfaces the smooth case, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Sariel Har-Peled , Shakhar Smorodinsky, On conflict-free coloring of points and simple regions in the plane, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Raphaëlle Chaine, A geometric convection approach of 3-D reconstruction, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	J. D. Boissonnat , S. Oudot, Provably good surface sampling and approximation, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Tamal K. Dey , Joachim Giesen , Samrat Goswami , Wulue Zhao, Shape dimension and approximation from samples, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.772-780, January 06-08, 2002, San Francisco, California
	Jeff Erickson, Local polyhedra and geometric graphs, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos , Tathagata Ray, Sampling and meshing a surface with guaranteed topology and geometry, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Pankaj Agarwal , Leonidas Guibas , An Nguyen , Daniel Russel , Li Zhang, Collision detection for deforming necklaces, Computational Geometry: Theory and Applications, v.28 n.2-3, p.137-163, June 2004
	Sunghee Choi, The Delaunay tetrahedralization from Delaunay triangulated surfaces, Proceedings of the eighteenth annual symposium on Computational geometry, p.145-150, June 05-07, 2002, Barcelona, Spain
	Yogish Sabharwal , Nishant Sharma , Sandeep Sen, Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions, Journal of Computer and System Sciences, v.72 n.6, p.955-977, September 2006
	Ho-Lun Cheng , Xinwei Shi, Quality mesh generation for molecular skin surfaces using restricted union of balls, Computational Geometry: Theory and Applications, v.42 n.3, p.196-206, April, 2009