## 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)

**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.