An optimal algorithm for closest pair maintenance (extended abstract)
- 1 January 1995
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 152-161
- https://doi.org/10.1145/220279.220296
Abstract
Given a set S of n points in i&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 algorithm is optimal up to constant factor because Q(log n) is lower bound, in algebraic decisiontree model of computation, on the time complexity of any algorithm that maintains the closest pair (for k = 1).Keywords
This publication has 0 references indexed in Scilit: