Abstract:
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 θ(n⌈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.