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

Research output: Contribution to journalArticlepeer-review

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 Δ has complexity O(Δ3). 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. We also generalize this upper bound to regular triangulations of k-ply systems of balls, unions of several dense point sets, and uniform samples of smooth surfaces. On the other hand, for any n and Δ = O(n), we construct a regular triangulation of complexity Ω(nΔ) whose n vertices have spread Δ.

Original languageEnglish (US)
Pages (from-to)83-115
Number of pages33
JournalDiscrete and Computational Geometry
Volume33
Issue number1
DOIs
StatePublished - Jan 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

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