Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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 Theta(n^(ceiling(d/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 < p <= d? 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.