Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/1429
Randomized data structures for the dynamic closestpair problem
Authors  Golin, M
Raman, R Schwarz, C Smid, M 


Issue Date  1998  
Source  SIAM journal on computing, v. 27, (4), 1998, AUG, p. 10361072  
Summary  We describe a new randomized data structure, the sparse partition, for solving the dynamic closestpair problem. Using this data structure the closest pair of a set of n points in Ddimensional 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.  
Subjects  
ISSN  00975397  
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 fulltext via Web of Science View fulltext via Scopus Files in this item:
