Nice point sets can have nasty Delaunay triangulations

Original · EN

We consider the complexity of Delaunay triangulations of sets of points in R³ 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 R³ with spread D has complexity Omega(minD³, nD, n²) and O(minD⁴, n²). For the case D = Theta(sqrtn), 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.