MPI-I-91-107

Let $V$ be a set of $n$ points in $k$-dimensional space. It is shown how the closest pair in $V$ can be maintained under insertions in $O(\log n \log\log n)$ amortized time, using $O(n)$ space. Distances are measured in the $L_{t}$-metric, where $1 \leq t \leq \infty$. This gives an $O(n \log n \log\log n)$ time on-line algorithm for computing the closest pair. The algorithm is based on Bentley's logarithmic method for decomposable searching problems. It uses a non-trivial extension of fractional cascading to $k$-dimensional space. It is also shown how to extend the method to maintain the closest pair during semi-online updates. Then, the update time becomes $O((\log n)^{2})$, even in the worst case.