The development of a randomized algorithm for the dynamic closest-pair problem

This talk describes the development of new randomized data structure, the {\em sparse-grid partition}, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of $n$ points in $k$-dimensional space, for any fixed $k$, can be found in constant time. The data structure supports insertions into and deletions from the set in expected $O(\log n)$ time and requires expected $O(n)$ space (assuming the updates are chosen by an adversary who does not know the random choices made by the data structure).\\ If time permits we will also discuss a new randomized incremental algorithm for the closest-pair problem that uses only O(1) expected time per insertion/deletion.\\ The above is joint work with with Rajeev Raman, Christian Schwarz and Michiel Smid.