Dense point sets have sparse Delaunay triangulations
<|reference_start|>Dense point sets have sparse Delaunay triangulations: 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 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.<|reference_end|>
@article{erickson2001dense,
    title={Dense point sets have sparse Delaunay triangulations},
    author={Jeff Erickson},
    journal={arXiv preprint arXiv:cs/0110030},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0110030},
    primaryClass={cs.CG cs.DM}
}