MPI-I-91-101

In the $k$-dimensional rectangular point location problem, we have to store a set of $n$ non-overlapping axes-parallel hyperrectangles in a data structure, such that the following operations can be performed efficiently: point location queries, insertions and deletions of hyperrectangles, and splitting and merging of hyperrectangles. A linear size data structure is given for this problem, allowing queries to be solved in $O((\log n)^{k-1} \log\log n )$ time, and allowing the four update operations to be performed in $O((\log n)^{2} \log\log n)$ amortized time. If only queries, insertions and split operations have to be supported, the $\log\log n$ factors disappear. The data structure is based on the skewer tree of Edelsbrunner, Haring and Hilbert and uses dynamic fractional cascading. This result is used to obtain a linear size data structure that maintains the closest pair in a set of $n$ points in $k$-dimensional space, when points are inserted. This structure has an $O((\log n)^{k-1})$ amortized insertion time. This leads to an on-line algorithm for computing the closest pair in a point set in $O( n (\log n)^{k-1})$ time.