DYNAMIC EUCLIDEAN MINIMUM SPANNING-TREES AND EXTREMA OF BINARY FUNCTIONS

We maintain the minimum spanning tree of a point set in the plane subj ect to point insertions and deletions, in amortized time O(n1/2 log2 n ) per update operation. We reduce the problem to maintaining bichromat ic closest pairs, which we solve in time O(n(epsilon)) per update. Our algorithm uses a novel construction, the ordered nearest neighbor pat h of a set of points. Our results generalize to higher dimensions, and to fully dynamic algorithms for maintaining minima of binary function s, including the diameter of a point set and the bichromatic farthest pair.