Nice point sets can have nasty delaunay triangulations

We consider the complexity of Delaunay triangulations of sets of points in IR³ under 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 IR³ with spread Δ has complexity Ω(min{Δ³,n Δ,n²}) and O(min{Δ⁴, n²}). For the case Δ = (√n), our lower bound construction consists of a uniform sample of a smooth convex surface with bounded curvature. We also construct a family of smooth connected surfaces such that the Delaunay triangulation of any good point sample has near-quadratic complexity.