Nice point sets can have nasty Delaunay triangulations

Proceedings of the 17th Annual ACM Symposium on Computational Geometry, 96-105, 2001.

arXiv:cs.CG/0103017

• Submitted journal version:
• Official journal version from Springer-Verlag (subscription required)

• SOCG version (© 2001 ACM):
• Official SOCG version from ACM's Digitial Library (subscription or $5 payment required)

• See also:
  • Arbitrarily large neighborly families of congruent symmetric convex 3-polytopes
  • Dense point sets have sparse Delaunay triangulations

Abstract:

We consider the complexity of Delaunay triangulations of sets of points with certain practical geometric constraints. The 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 3-space with spread D has complexity Omega(min{D³, nD, n²}) and O(min{D⁴, n²}). For the case D=sqrt{n}, our lower bound construction consists of a grid-like sample of a right circular cylinder with constant height and radius. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.

• Note: Lemma 2.1 in this paper (the source of the picture above) was independently proven by Daciana Bochis and Francisco Santos. See Lemma 4.2 of their paper "On the number of facets of three- dimensional Dirichlet stereohedra II: Non-cubic groups".

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 01 Jul 2003