Dynamic Euclidean minimum spanning trees and extrema of binary functions

This work maintains the minimum spanning tree of a point set in the plane subject to point insertions and deletions, in amortized timeO(n1/2 log2n) per update operation, and uses a novel construction, theordered nearest neighbor path of a set of points.

Abstract

We maintain the minimum spanning tree of a point set in the plane subject to point insertions and deletions, in amortized timeO(n 1/2 log2 n) per update operation. We reduce the problem to maintaining bichromatic closest pairs, which we solve in timeO(n e ) per update. Our algorithm uses a novel construction, theordered nearest neighbor path of a set of points. Our results generalize to higher dimensions, and to fully dynamic algorithms for maintaining minima of binary functions, including the diameter of a point set and the bichromatic farthest pair.