An Optimal Algorithm for Closest-Pair Maintenance

Abstract

Given a set S of n points in k-dimensional space, and an Lt metric, the 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 point). For fixed dimension k and fixed metric Lt, we give a data structure of size O(n) that maintains a closest pair of S in O(log n) time per insertion and deletion. The running time of the algorithm is optimal up to a constant factor because Ω(log n) is a lower bound, in an algebraic decision-tree model of computation, on the time complexity of any algorithm that maintains the closest pair (for k = 1). The algorithm is based on the fair-split tree. The constant factor in the update time is exponential in the dimension. We modify the fair-split tree to reduce it.