Abstract
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~$\Real^3$ with spread $\Delta$ has complexity $O(\Delta^3)$. This bound is tight in the worst case for all $\Delta = 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 $\Delta = O(n)$, we construct a regular triangulation of complexity $\Omega(n\Delta)$ whose $n$ vertices have spread $\Delta$.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Erickson, J. Dense Point Sets Have Sparse Delaunay Triangulations or “... But Not Too Nasty”. Discrete Comput Geom 33, 83–115 (2005). https://doi.org/10.1007/s00454-004-1089-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-004-1089-3