Dense point sets have sparse delaunay triangulations or "... but not too nasty"

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ℝ3 with spread A has complexity 0(Δ3). This bound is tight in the worst case for all Δ = 0(y√n). In particular, the Delaunay triangulation of any dense point set has linear complexity. On the other hand, for any ν and Δ -0(ν), we construct a regular triangulation of complexity Ω-(νΔ) whose n vertices have spread A.

Original languageEnglish (US)
Title of host publicationProceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PublisherAssociation for Computing Machinery
Pages125-134
Number of pages10
ISBN (Electronic)089871513X
StatePublished - 2002
Event13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 - San Francisco, United States
Duration: Jan 6 2002Jan 8 2002

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume06-08-January-2002

Other

Other13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
Country/TerritoryUnited States
CitySan Francisco
Period1/6/021/8/02

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Dense point sets have sparse delaunay triangulations or "... but not too nasty"'. Together they form a unique fingerprint.

Cite this