Dense point sets have sparse Delaunay triangulations: or "…but not too nasty"
Jeff Erickson · Symposium on Discrete Algorithms · 2002
The spread of a finite set of points is the ratio between the longest and shortest pairwise distances. We prove that the Delaunay triangulation of any set of n points in IR3 with spread Δ has complexity O(Δ3). This bound is tight in the worst case for all Δ = O(√n). In particular, the Delaunay triangulation of any dense point set has linear complexity. On the other hand, for any n and Δ = O(n), we construct a regular triangulation of complexity Ω(nΔ) whose n vertices have spread Δ.