Dense point sets have sparse Delaunay triangulations: or "…but not too nasty"

ABSTRACT

The spread of a finite set of points is the ratio between the longest and shortest pairwise distances. We prove that the Delaunay triangulation of any set of n points in IR³ with spread Δ has complexity O(Δ³). This bound is tight in the worst case for all Δ = O(√n). In particular, the Delaunay triangulation of any dense point set has linear complexity. On the other hand, for any n and Δ = O(n), we construct a regular triangulation of complexity Ω(nΔ) whose n vertices have spread Δ.

REFERENCES

• 1: Pankaj K. Agarwal , Herbert Edelsbrunner , Otfried Schwarzkopf , Emo Welzl, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete & Computational Geometry, v.6 n.5, p.407-422, 1991 [doi>10.1007/BF02574698]
• 2: P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. Advances in Discrete and Computational Geometry, 1-56, 1999. Contemporary Mathematics 223, American Mathematical Society.
• 3: Alok Aggarwal , Prabhakar Raghavan, Deferred data structure for the nearest neighbor problem, Information Processing Letters, v.40 n.3, p.119-122, Nov. 1991 [doi>10.1016/0020-0190(91)90164-D]
• 4: N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22(4):481-504, 1999.
• 5: 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]
• 6: 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]
• 7: N. Amenta, S. Choi, and R. Kolluri. The power crust, unions of balls, and the medial axis transform. Internat. J. Comput. Geom. Appl. 19(2-3):127-153, 2001.
• 8: D. Attali and J.-D. Boissonnat. Complexity of Delaunay triangulations of points on polyhedral surfaces. Rapport de recherche 4015, INRIA Sophia-Antipolis, July 2001. (http://www.inria.fr/rrrt/rr-4232.html).
• 9: Mark de Berg, Ray Shooting, Depth Orders and Hidden Surface Removal, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 10: 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]
• 11: Mark de Berg , Mark Overmars , Otfried Schwarzkopf, Computing and Verifying Depth Orders, SIAM Journal on Computing, v.23 n.2, p.437-446, April 1994 [doi>10.1137/S0097539791223747]
• 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: K. Q. Brown. Voronoi diagrams from convex hulls. Inform. Process. Lett. 9(5):223-228, 1979.
• 14: 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]
• 15: David E. Cardoze , Leonard J. Schulman, Pattern Matching for Spatial Point Sets, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.156, November 08-11, 1998
• 16: T. M. Chan, J. Snoeyink, and C. K. Yap. Primal dividing and dual pruning: Output-sensitive construction of 4-d polytopes and 3-d Voronoi diagrams. Discrete Comput. Geom. 18:433-454, 1997.
• 17: Bernard Chazelle, Cutting hyperplanes for divide-and-conquer, Discrete & Computational Geometry, v.9 n.2, p.145-158, 1993 [doi>10.1007/BF02189314]
• 18: B. Chazelle, H. Edelsbrunner, L. J. Guibas, M. Sharir, and J. Stolfi. Lines in space: Combinatorics and algorithms. Algorithmica 15:428-447, 1996.
• 19: H.-L. Cheng, T. K. Dey, H. Edelsbrunner, and J. Sullivan. Dynamic skin triangulation. Discrete Comput. Geom. 25(4):525-568, 2001.
• 20: 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]
• 21: K Clarkson, A probabilistic algorithm for the post office problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.175-184, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22165]
• 22: Kenneth L. Clarkson, A randomized algorithm for closest-point queries, SIAM Journal on Computing, v.17 n.4, p.830-847, August 1988 [doi>10.1137/0217052]
• 23: K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete Comput. Geom. 22:63-93, 1999.
• 24: O. Devillers, S. Meiser, and M. Teillaud. The space of spheres, a geometric tool to unify duality results on Voronoi diagrams. Report 1620, INRIA Sophia-Antipolis, 1992. (http://www.inria.fr/rrrt/rr-1620.html).
• 25: A. K. Dewdney and J. K. Vranch. A convex partition of R3 with applications to Crum's problem and Knuth's post-office problem. Utilitas Math. 12:193-199, 1977.
• 26: T. K. Dey, S. Funke, and E. A. Ramos. Surface reconstruction in almost linear time under locally uniform sampling. Abstracts 17th European Workshop Comput. Geom., 129-132, 2001. Freie Universität Berlin. (http://www.cis.ohio-state.edu/~tamaldey/paper/recon-linear/surf.ps.gz).
• 27: R. Dwyer. The expected number of k-faces of a Voronoi diagram. Internat. J. Comput. Math. 26(5):13-21, 1993.
• 28: 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]
• 29: H. Edelsbrunner. An acyclicity theorem for cell complexes in d dimensions. Combinatorica 10(3):251-260, 1990.
• 30: H. Edelsbrunner. Deformable smooth surface design. Discrete Comput. Geom. 21:87-115, 1999.
• 31: Geometry and topology for mesh generation, Cambridge University Press, New York, NY, 2001
• 32: 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]
• 33: H. Edelsbrunner, P. Valtr, and E. Welzl. Cutting dense point sets in half. Discrete Comput. Geom. 17:243-255, 1997.
• 34: Jeff Erickson, Space-Time Tradeoffs for Emptiness Queries, SIAM Journal on Computing, v.29 n.6, p.1968-1996, April 2000 [doi>10.1137/S0097539798337212]
• 35: Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378636]
• 36: 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
• 37: Martin Gavrilov , Piotr Indyk , Rajeev Motwani , Suresh Venkatasubramanian, Geometric pattern matching: a performance study, Proceedings of the fifteenth annual symposium on Computational geometry, p.79-85, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304916]
• 38: M. J. Golin and H. S. Na. On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes. Proc. 12th Canad. Conf. Comput. Geom., 127-135, 2000. (http://www.cs.unb.ca/conf/cccg/eProceedings/).
• 39: M. J. Golin and H. S. Na. On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes. Tech. Rep. HKUST-TCSC-2001-08, Hong Kong Univ. Sci. Tech., June 2001. (http://www.cs.ust.hk/tcsc/RR/2001-08.ps.gz).
• 40: M. J. Golin and H. S. Na. On the proofs of two lemmas describing the intersections of spheres with the boundary of a convex polytope. Tech. Rep. HKUST-TCSC-2001-09, Hong Kong Univ. Sci. Tech., July 2001. (http://www.cs.ust.hk/tcsc/RR/2001-09.ps.gz).
• 41: J. E. Goodman , R. Pollack , B. Sturmfels, Coordinate representation of order types requires exponential storage, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.405-410, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73046]
• 42: J. E. Goodman, R. Pollack, and B. Sturmfels. The intrinsic spread of a configuration in Rd. J. Amer. Math. Soc. 3:639-651, 1990.
• 43: L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 7:381-413, 1992.
• 44: D. Hilbert and S. Cohn-Vossen. Geometry and the Imagination. Chelsea Publishing Company, New York, NY, 1952.
• 45: 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]
• 46: Mary Inaba , Naoki Katoh , Hiroshi Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract), Proceedings of the tenth annual symposium on Computational geometry, p.332-339, June 06-08, 1994, Stony Brook, New York, United States [doi>10.1145/177424.178042]
• 47: Piotr Indyk , Rajeev Motwani , Suresh Venkatasubramanian, Geometric matching under noise: combinatorial bounds and algorithms, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.457-465, January 17-19, 1999, Baltimore, Maryland, United States
• 48: Drago Krznaric , Christos Levcopoulos, Computing Hierarchies of Clusters from the Euclidean Minimum Spanning Tree in Linear Time, Proceedings of the 15th Conference on Foundations of Software Technology and Theoretical Computer Science, p.443-455, December 18-20, 1995
• 49: Xiang-Yang Li , Shang-Hua Teng, Generating well-shaped Delaunay meshed in 3D, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.28-37, January 07-09, 2001, Washington, D.C., United States
• 50: J. Matoušek. Range searching with efficient hierarchical cuttings. Discrete Comput. Geom. 10(2):157-182, 1993.
• 51: Gary L. Miller , Dafna Talmor , Shang-Hua Teng, Optimal coarsening of unstructured meshes, Journal of Algorithms, v.31 n.1, p.29-65, April 1999 [doi>10.1006/jagm.1998.0990]
• 52: Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.683-692, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225286]
• 53: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
• 54: Thomas Schreiber, A Voronoi Diagram Based Adaptive K-Means-Type Clustering Algorithm for Multidimenstional Weighted Data, Proceedings of the International Workshop on Computational Geometry - Methods, Algorithms and Applications, p.265-275, March 21-22, 1991
• 55: 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]
• 56: 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]
• 57: W. Thurston. Three-Dimensional Geometry and Topology, Volume 1. Princeton University Press, New Jersey, 1997.
• 58: W. P. Thurston. The geometry and topology of 3-manifolds. Mathematical Sciences Research Institite, Berkeley, CA, 1997. (http://msri.org/publications/books/gt3m/).
• 59: Pavel Valtr, Convex independent sets and 7-holes in restricted planar point sets, Discrete & Computational Geometry, v.7 n.2, p.135-152, 1992 [doi>10.1007/BF02187831]
• 60: P. Valtr. Planar point sets with bounded ratios of distances. Ph.D. thesis, Fachbereich Mathematik, Freie Universität Berlin, Berlin, Germany, 1994.
• 61: P. Valtr. Lines, line-point incidences and crossing families in dense sets. Combinatorica 16:269-294, 1996.
• 62: K. Verbarg. Approximate center points in dense point sets. Abstracts 13th European Workshop Comput. Geom., 55-56, 1997. Universität Würzburg.
• 63: J. Vleugels. On Fatness and Fitness --- Realistic Input Models for Geometric Algorithms. Ph.D. thesis, Dept. Comput. Sci., Univ. Utrecht, Utrecht, The Netherlands, 1997.