HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Journal/Magazine Articles >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/1429
Title: Randomized data structures for the dynamic closest-pair problem
Authors: Golin, Mordecai J.
Raman, Rajeev
Schwarz, Christian
Smid, Michiel
Keywords: Computational geometry
Proximity
Dynamic data structures
Randomization
Issue Date: Aug-1998
Citation: SIAM journal on computing, v. 27, no. 4, Aug. 1998, p. 1036-1072
Abstract: 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(log2 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 in not determined in any way by the random choices made by the algorithm.
Rights: Copyright © SIAM. This paper is made available with permission of the Society for Industrial and Applied Mathematics for limited noncommerical distribution only.
URI: http://hdl.handle.net/1783.1/1429
Appears in Collections:CSE Journal/Magazine Articles

Files in This Item:

File Description SizeFormat
27771.pdf393KbAdobe PDFView/Open

Find published version via OpenURL Link Resolver

All items in this Repository are protected by copyright, with all rights reserved.