Please use this identifier to cite or link to this item:

Randomized data structures for the dynamic closest-pair problem

Authors Golin, Moedecai Jay
Raman, R.
Schwarz, C.
Smid, M.
Issue Date 1998
Source SIAM journal on computing , v. 27, (4), 1998, AUG, p. 1036-1072
Summary 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(log(2) n) 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.
ISSN 0097-5397
Rights Copyright © SIAM. This paper is made available with permission of the Society for Industrial and Applied Mathematics for limited noncommerical distribution only.
Language English
Format Article
Access View full-text via Web of Science
View full-text via Scopus
Files in this item:
File Description Size Format
27771.pdf 402537 B Adobe PDF