ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. Given a set S of n points in {k} -dimensional space, and an L t 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 L t , 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009340
Permalink
