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

Fully dynamic maintenance of euclidean minimum spanning trees

  • Author(s): Eppstein, David
  • et al.

We maintain the minimum spanning tree of a point set in the plane, subject to point insertions and deletions, in time O(n^5/6 log1^2/2 n) per update operation. No nontrivial dynamic geometric minimum spanning tree algorithm was previously known. We reduce the problem to maintaining bichromatic closest pairs, which we also solve in the same time bounds. 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.

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