Skip to main content
eScholarship
Open Access Publications from the University of California

Fully dynamic maintenance of Euclidean minimum spanning trees and maxima of decomposable functions

Abstract

We maintain the minimum spanning tree of a point set in the plane, subject to point insertions and deletions, in time O(n^1/2 log^2 n) per update operation. We reduce the problem to maintaining bichromatic closest pairs, which we solve in time O(n^E) per update. Our algorithm uses a novel construction, the ordered nearest neighbors of a sequence of points. Any point set or bichromatic point set can be ordered so that this graph is a simple path. Our results generalize to higher dimensions, and to fully dynamic algorithms for maintaining maxima of decomposable functions, including the diameter of a point set and the bichromatic farthest pair.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View