Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/111916
Title: An Optimal Algorithm for Closest-Pair Maintenance
Authors: Bespamyatnikh, S. N.
Issue Date: 1998
Publisher: Springer New York
Springer Science and Business Media LLC
Citation: Bespamyatnikh S. N. An Optimal Algorithm for Closest-Pair Maintenance / S. N. Bespamyatnikh. — DOI 10.17323/1728-192x-2020-3-130-166 // Discrete and Computational Geometry. — 1998. — Vol. 19. — Iss. 2. — P. 175-195.
Abstract: Given a set S of n points in k-dimensional space, and an Lt 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 Lt, 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.
URI: http://hdl.handle.net/10995/111916
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 0032389558
ISSN: 0179-5376
DOI: 10.17323/1728-192x-2020-3-130-166
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-0032389558.pdf203,94 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.