## October 10, Fall 2008: Theory Seminar

### 1:00pm in 253 ICS

# > Self-Improving Algorithms for Delaunay Triangulations

##
Ken Clarkson, IBM Almaden Research Center

This work investigates ways in which an algorithm can improve its
expected performance by fine-tuning itself automatically, with respect
to an arbitrary and unknown input distribution. We give such
self-improving algorithms for sorting and for computing Delaunay
triangulations. Each algorithm begins with a training phase during which
it adjusts itself to the input distribution, followed by a stationary
regime in which the algorithm settles to its optimized incarnation. We
show that in both cases, in the stationary regime, the algorithms run as
fast as possible.

Joint work with Nir Alon, Bernard Chazelle, Ding Liu, C. Seshadhri, and
Wolfgang Mulzer.