Eppstein (1995) gave a technique to transform any data structure for dynamic nearest neighbor queries into a data structure for dynamic closest pair, for any distance function; the transformation increases the time bound by two logarithmic factors. We present a similar, simple transformation that is just as good, and can avoid the extra logarithmic factors when the query and update time of the given structure exceed n~ε for some constant ε > 0. Consequently, in the case of an arbitrary distance function, we obtain an optimal O(n)-space data structure to maintain the dynamic closest pair of n points in O(n) amortized time plus O(n) distance evaluations per update.
展开▼
