Dense point sets have sparse Delaunay triangulations
| dc.creator | Erickson, Jeff | |
| dc.date | 2001-10-15 | |
| dc.date | 2002-11-08 | |
| dc.date.accessioned | 2026-07-07T03:17:47Z | |
| dc.date.available | 2026-07-07T03:17:47Z | |
| dc.description | 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 R^3 with spread D has complexity O(D^3). This bound is tight in the worst case for all D = O(sqrt{n}). In particular, the Delaunay triangulation of any dense point set has linear complexity. We also generalize this upper bound to regular triangulations of k-ply systems of balls, unions of several dense point sets, and uniform samples of smooth surfaces. On the other hand, for any n and D=O(n), we construct a regular triangulation of complexity Omega(nD) whose n vertices have spread D. | |
| dc.description | 31 pages, 11 figures. Full version of SODA 2002 paper. Also available at http://www.cs.uiuc.edu/~jeffe/pubs/screw.html | |
| dc.identifier | https://arxiv.org/abs/cs/0110030 | |
| dc.identifier | http://arxiv.org/abs/cs/0110030 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/30857 | |
| dc.subject | Computational Geometry | |
| dc.subject | Discrete Mathematics | |
| dc.subject | F.2.2, G.2.m | |
| dc.title | Dense point sets have sparse Delaunay triangulations | |
| dc.type | text |