TY - GEN

T1 - Dense point sets have sparse delaunay triangulations or "... but not too nasty"

AU - Erickson, Jeff

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84968791828&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84968791828&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84968791828

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 125

EP - 134

BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

PB - Association for Computing Machinery

T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002

Y2 - 6 January 2002 through 8 January 2002

ER -