Nice point sets can have nasty Delaunay triangulations
| dc.creator | Erickson, Jeff | |
| dc.date | 2001-03-23 | |
| dc.date.accessioned | 2026-07-07T03:17:01Z | |
| dc.date.available | 2026-07-07T03:17:01Z | |
| dc.description | 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. | |
| dc.description | 11 pages, 8 figures, to appear in Proc. SCG '01 | |
| dc.identifier | https://arxiv.org/abs/cs/0103017 | |
| dc.identifier | http://arxiv.org/abs/cs/0103017 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30570 | |
| dc.subject | Computational Geometry | |
| dc.subject | F.2.2;G.2.m | |
| dc.title | Nice point sets can have nasty Delaunay triangulations | |
| dc.type | text |