The Tech. Report used the more informative title "Updating widths and maximum spanning trees using the rotating caliper graph", which I also used for the journal submission, but the referees made me change it back. Dynamic geometry in a model of Mulmuley and Schwarzkopf in which insertions and deletions are chosen randomly among a worst-case pool of points. This paper introduces several fundamental techniques including the rotating caliper graph of a point set and a method for performing decomposible range queries in the average case setting. It has also since inspired the use of a similar model in dynamic graph algorithms.
(BibTeX -- SODA paper -- Full paper -- Citations -- CiteSeer -- ACM DL)
Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine
Semi-automatically filtered from a common source file.