Return to Colloquia & Seminar listing

### Complexity of the Delaunay triangulation in Higher-Dimensional Space

**Algebra & Discrete Mathematics**

Speaker: | Nina Amenta, UC Davis |

Location: | 2112 MSB |

Start time: | Fri, Oct 24 2008, 2:10PM |

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.