Nice point sets can have nasty Delaunay triangulations

Discrete & Computational Geometry 30(1):109-132, 2003.
(Special issue of invited papers from the 17th Annual ACM Symposium on Computational Geometry)

Proceedings of the 17th Annual ACM Symposium on Computational Geometry, 96-105, 2001.


We consider the complexity of Delaunay triangulations of sets of points with 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 3-space with spread D has complexity Omega(min{D3, nD, n2}) and O(min{D4, n2}). For the case D=sqrt{n}, our lower bound construction consists of a grid-like sample of a right circular cylinder with constant height and radius. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.

Publications - Jeff Erickson ( 01 Jul 2003