ICS Theory Group

CompSci 269S, Winter 2008: Theory Seminar

Feb 22, 2008, 1:00pm in Bren Hall 1423

On the Complexity of Delaunay Triangulations on Manifolds

Nina Amenta (UC Davis)


Even more than most spatial data structures, the Delaunay triangulation suffers from the "curse of dimensionality". A classic theorem of McMullen says that the worst-case complexity of the Delaunay triangulation of a set of n points in dimension d is θ(nd/2⌉). The point sets constructed to realize this exponential bound are distributed on one-dimensional curves. What about distributions of points on manifolds of dimension 1 < pd

We consider sets of points distributed nearly uniformly on a polyhedral surfaces of dimension p, and find that their Delaunay triangulations have complexity O(n(d-k+1)/p), with k being the ceiling of (d+1)/(p+1), and we show that this bound is tight.