Return to Colloquia & Seminar listing
Biased Randomized Insertion Orders
Algebra & Discrete Mathematics| Speaker: | Nina Amenta, UC Davis CS dept. |
| Location: | 593 Kerr |
| Start time: | Thu, Apr 3 2003, 12:00PM |
Description
The most popular algorithm for constructing a Delaunay
triangulation is to maintain the triangulation while adding points one
by one in random order. The randomness is important for proving that the
running time is optimal, but ironically it makes the programs run really
slowly because of poor memory performance. We define an insertion order
that is random enough that we still can prove optimality, but allows us
the freedom to improve the memory access patterns and the "real life"
running time dramatically. We will concentrate in this talk on the proof
of optimality, which uses bounds on the number of k-sets for spheres in
3D.