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

Updating widths and maximum spanning trees using the rotating caliper graph

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

We maintain the maximum spanning tree of a planar point set, as points are inserted or deleted, in O(log^3 n) time per update in Mulmuley's expected-case model of dynamic geometric computation. We use as subroutines dynamic algorithms for two other geometric graphs: the farthest neighbor forest and the rotating caliper graph related to an algorithm for static computation of point set widths and diameters. We maintain the former graph in time O(log^2 n) per update and the latter in time O(log n) per update. We also use the rotating caliper graph to maintain the diameter, width, and minimum enclosing rectangle in time O(log n) per update. A subproblem uses a technique for expected-case orthogonal range search that may also be of interest.

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