Nice point sets can have nasty Delaunay triangulations
<|reference_start|>Nice point sets can have nasty Delaunay triangulations: We consider the complexity of Delaunay triangulations of sets of points in R^3 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^3 with spread D has complexity Omega(min{D^3, nD, n^2}) and O(min{D^4, n^2}). For the case D = Theta(sqrt{n}), 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.<|reference_end|>
@article{erickson2001nice,
    title={Nice point sets can have nasty Delaunay triangulations},
    author={Jeff Erickson},
    journal={arXiv preprint arXiv:cs/0103017},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0103017},
    primaryClass={cs.CG}
}