2001/03/23 by Jeff Erickson, Erickson, Jeff · 1 citation
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #F.2.2 #FOS: Computer and information sciences #G.2.m #cs.CG
paper · pdf · doi:10.48550/arxiv.cs/0103017
11 pages, 8 figures, to appear in Proc. SCG '01
arxiv created 2001/03/23 · openalex publication_date 2001/03/23 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the complexity of Delaunay triangulations of sets of points in R3 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 R3 with spread D has complexity Omega(minD3, nD, n2) and O(minD4, n2). For the case D = Theta(sqrtn), 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.