Abstract
We consider the complexity of Delaunay triangulations of sets of points in IR3 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 IR3 with spread Δ has complexity Ω(min{Δ3,n Δ,n2}) and O(min{Δ4, n2}). For the case Δ = (√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.
| Original language | English (US) |
|---|---|
| Pages | 96-105 |
| Number of pages | 10 |
| DOIs | |
| State | Published - 2001 |
| Event | 17th Annual Symposium on Computational Geometry (SCG'01) - Medford, MA, United States Duration: Jun 3 2001 → Jun 5 2001 |
Other
| Other | 17th Annual Symposium on Computational Geometry (SCG'01) |
|---|---|
| Country/Territory | United States |
| City | Medford, MA |
| Period | 6/3/01 → 6/5/01 |
Keywords
- Delaunay triangulation
- Lower bounds
- Sample measure
- Spread
- Surface reconstruction
- ε-sample
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics