@inproceedings{819f97312a5d4886aa372ad7b64ffe43,
title = "Dense point sets have sparse delaunay triangulations or {"}... but not too nasty{"}",
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 ℝ3 with spread A has complexity 0(Δ3). This bound is tight in the worst case for all Δ = 0(y√n). In particular, the Delaunay triangulation of any dense point set has linear complexity. On the other hand, for any ν and Δ -0(ν), we construct a regular triangulation of complexity Ω-(νΔ) whose n vertices have spread A.",
author = "Jeff Erickson",
year = "2002",
language = "English (US)",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "125--134",
booktitle = "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002",
address = "United States",
note = "13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002 ; Conference date: 06-01-2002 Through 08-01-2002",
}