Nice point sets can have nasty delaunay triangulations

Research output: Contribution to conferencePaperpeer-review


We consider the complexity of Delaunay triangulations of sets of points in IR3 under 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 IR3 with spread Δ has complexity Ω(min{Δ3,n Δ,n2}) and O(min{Δ4, n2}). For the case Δ = (√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.

Original languageEnglish (US)
Number of pages10
StatePublished - 2001
Event17th Annual Symposium on Computational Geometry (SCG'01) - Medford, MA, United States
Duration: Jun 3 2001Jun 5 2001


Other17th Annual Symposium on Computational Geometry (SCG'01)
Country/TerritoryUnited States
CityMedford, MA


  • Delaunay triangulation
  • Lower bounds
  • Sample measure
  • Spread
  • Surface reconstruction
  • ε-sample

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Nice point sets can have nasty delaunay triangulations'. Together they form a unique fingerprint.

Cite this