**Average case analysis of dynamic geometric optimization**.

D. Eppstein.

Tech. Rep. 93-18, ICS, UCI, 1993.

*5th ACM-SIAM Symp. Discrete Algorithms,*Arlington, 1994, pp. 77–86.

*Comp. Geom. Theory & Applications*6: 45–68, 1996.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.