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

To appear in Discrete & Computational Geometry.

• Download revised journal version:
• Official journal version from Springer (subscription required)
  Note: The full version contains several results that were not in the SODA paper, especially in Sections 2 and 4.

• Download SODA version (© 2002 SIAM):
• Download abstract from the 11th Fall Workshop on Computational Geometry:

• See also: Nice point sets can have nasty Delaunay triangulations

Abstract:

The spread of a set of points is the ratio between the largest ans smallest pairwise distances. We show that the Delaunay triangulation of any set of n points in R³ with spread D has complexity O(D³). This bound is tight in the worst case for all D=O(sqrt{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 any D=O(n), we construct a regular triangulation of complexity Omega(nD) whose n vertices have spread D.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 14 Sep 2004