Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://elar.urfu.ru/handle/10995/111916
Название: | An Optimal Algorithm for Closest-Pair Maintenance |
Авторы: | Bespamyatnikh, S. N. |
Дата публикации: | 1998 |
Издатель: | Springer New York Springer Science and Business Media LLC |
Библиографическое описание: | 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. |
Аннотация: | 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://elar.urfu.ru/handle/10995/111916 |
Условия доступа: | info:eu-repo/semantics/openAccess |
Идентификатор SCOPUS: | 0032389558 |
Идентификатор WOS: | 000071610500003 |
Идентификатор PURE: | 53655173 |
ISSN: | 0179-5376 |
DOI: | 10.17323/1728-192x-2020-3-130-166 |
Располагается в коллекциях: | Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC |
Файлы этого ресурса:
Файл | Описание | Размер | Формат | |
---|---|---|---|---|
2-s2.0-0032389558.pdf | 203,94 kB | Adobe PDF | Просмотреть/Открыть |
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.