- 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.
(SODA paper – Full paper)