Nice point sets can have nasty Delaunay triangulations

Details Nice point sets can have nasty Delaunay triangulations Nice point sets can have nasty Delaunay triangulations

2001-03-23

arxiv.org/abs/cs/0103017v1

Computer Science

Computational Geometry

11 pages, 8 figures, to appear in Proc. SCG '01

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Nice point sets can have nasty 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 Nice point sets can have nasty Delaunay triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nice point sets can have nasty Delaunay triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-192706