Nice point sets can have nasty delaunay triangulations

Research output: Contribution to conferencePaper

Abstract

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)
Pages96-105
Number of pages10
StatePublished - Jan 1 2001
Event17th Annual Symposium on Computational Geometry (SCG'01) - Medford, MA, United States
Duration: Jun 3 2001Jun 5 2001

Other

Other17th Annual Symposium on Computational Geometry (SCG'01)
CountryUnited States
CityMedford, MA
Period6/3/016/5/01

    Fingerprint

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Cite this

Erickson, J. G. (2001). Nice point sets can have nasty delaunay triangulations. 96-105. Paper presented at 17th Annual Symposium on Computational Geometry (SCG'01), Medford, MA, United States.