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

Fully dynamic maintenance of euclidean minimum spanning trees

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

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
Current View