- Dynamic algorithms for
half-space reporting, proximity problems, and geometric minimum
spanning trees, FOCS 1992. (With P. Agarwal and
J. Matousek.) The initial appearance of my closest pair data
structure, together with results of Agarwal and Matousek on range
searching.
- Dynamic Euclidean
minimum spanning trees and extrema of binary functions,
*Disc. Comp. Geom.*1995. The journal version of my part of the FOCS '92 paper. - Average case
analysis of dynamic geometric optimization, Tech. Rep. 1993,
SODA 1994,
*Comp. Geom. Th. & Appl.*1996. Includes algorithms for maintaining planar farthest pairs. - Fast hierarchical clustering and
other applications of dynamic closest pairs, SODA 1998,
*JEA*2000, cs.DS/9912014. Non-geometric applications of my closest pair data structure. -
Raising roofs, crashing cycles, and playing pool: applications of a
data structure for finding pairwise interactions (with Jeff Erickson), SCG 1998,
*Disc. Comp. Geom.*1999. We use closest pairs to solve collision detection, offset curve construction, and skeletonization problems. - Incremental and
decremental maintenance of planar width, SODA 1999,
cs.CG/9909038,
*J. Algorithms*2000. Keeps track of the width of a point set by turning it into a dynamic bichromatic closest pair problem on the set of convex hull features. - Lazy
algorithms for dynamic closest pair with arbitrary distance
measures
(with J. Cardinal),
Tech. Rep. 502, Univ. Libre de Bruxelles, 2003. Adds a lazy deletion
mechanism to my previous closest pair data structures and shows
experimentally that it enhances their performance.

David Eppstein, Information & Computer Science, UC Irvine, .