Randomized data structures for the dynamic closest-pair problem

We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional space, for any xed D, can be found in constant time. If a frame containing all the points is known in advance, and if the ∞oor function is available at unit cost, then the data structure supports insertions into and deletions from the set in expected O(logn) time and requires expected O(n) space. This method is more ecient than any deterministic algorithm for solving the problem in dimension D> 1. The data structure can be modied to run in O(log 2 n) expected time per update in the algebraic computation tree model. Even this version is more ecient than the best currently known deterministic algorithm for D> 2. Both results assume that the sequence of updates is not determined in any way by the random choices made by the algorithm.