CSAIL Event Calendar: Previous Series
|
Delaunay triangulations of points on manifolds Speaker: Nina Amenta , University of California at Davis Relevant URL: http://theory.lcs.mit.edu/theory-seminars/calendar.html Like 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, while for points distributed uniformly in space the complexity is O(n). 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-1)/p)). See other events that are part of Theory Colloquium Spring 2007 |
