Dense point sets have sparse Delaunay triangulations

Details Dense point sets have sparse Delaunay triangulations Dense point sets have sparse Delaunay triangulations

2001-10-15

arxiv.org/abs/cs/0110030v2

Computer Science

Computational Geometry

31 pages, 11 figures. Full version of SODA 2002 paper. Also available at http://www.cs.uiuc.edu/~jeffe/pubs/screw.html

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Dense point sets have sparse Delaunay triangulations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dense point sets have sparse Delaunay triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dense point sets have sparse Delaunay triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-621740