2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/30857The 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 R^3 with spread D has complexity O(D^3). This bound is tight in the worst case for all D = O(sqrt{n}). In particular, the Delaunay triangulation of any dense point set has linear complexity. We also generalize this upper bound to regular triangulations of k-ply systems of balls, unions of several dense point sets, and uniform samples of smooth surfaces. On the other hand, for any n and D=O(n), we construct a regular triangulation of complexity Omega(nD) whose n vertices have spread D.31 pages, 11 figures. Full version of SODA 2002 paper. Also available at http://www.cs.uiuc.edu/~jeffe/pubs/screw.htmlComputational GeometryDiscrete MathematicsF.2.2, G.2.mtext