Proceedings of the 17th Annual ACM Symposium on Computational Geometry, 96-105, 2001.
Abstract:
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{D^{3}, nD, n^{2}}) and O(min{D^{4}, n^{2}}). 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.
- Note: Lemma 2.1 in this paper (the source of the picture above) was independently proven by Daciana Bochis and Francisco Santos. See Lemma 4.2 of their paper "On the number of facets of three- dimensional Dirichlet stereohedra II: Non-cubic groups".