AN OPTIMAL ALGORITHM FOR CLOSEST-PAIR MAINTENANCE

Given a set S of n points in k-dimensional space, and an L., metric, t he dynamic closest-pair problem is defined as follows: find a closest pair of S after each update of S (the insertion or the deletion of a p oint). For fixed dimension k and fixed metric L-t, we give a data stru cture of size O(n) that maintains a closest pair of S in O (log n) tim e per insertion and deletion. The running time of the algorithm is opt imal up to a constant factor because Omega(log n) is a lower bound, in an algebraic decision-tree model of computation, on the time complexi ty of any algorithm that maintains the closest pair (for k = 1). The a lgorithm is based on the fair-split tree. The constant factor in the u pdate time is exponential in the dimension. We modify the fair-split t ree to reduce it.