- 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, 03 Sep 2003, 19:46:40 PDT.