Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.