1998/08/01 by Mordecai J. Golin, Rajeev Raman, Christian Schwarz +1 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data structure #Randomized algorithm #Mathematics #Deterministic algorithm #Combinatorics #Binary logarithm #Sequence (biology) #Algorithm #Dimension (graph theory) #Set (abstract data type) #Tree (set theory) #Amortized analysis #Discrete mathematics #Computer science
paper · doi:10.1137/s0097539794277718
openalex publication_date 1998/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/02
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 fixed D, can be found in constant time. If a frame containing all the points is known in advance, and if the floor function is available at unit cost, then the data structure supports insertions into and deletions from the set in expected O(log n) time and requires expected O(n) space. This method is more efficient than any deterministic algorithm for solving the problem in dimension D > 1. The data structure can be modified to run in O(log2n) expected time per update in the algebraic computation tree model. Even this version is more efficient 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.