Dynamic algorithms for half-space reporting, proximity problems, and geometric minimum spanning trees

Pankaj Kumar Agarwal, David Eppstein, and Jiří Matoušek
Proc. 33rd Symp. Foundations of Computer Science, IEEE, Oct 1992, pp. 80–89
http://www.ics.uci.edu/~eppstein/pubs/AgaEppMat-FOCS-92.pdf

Cited by:

• Dynamic algebraic algorithms
• On geometric optimization with few violated constraints
• Geometric range searching
• Dynamic half-space range reporting and its applications
• Finding $k$ farthest pairs and $k$ closest/farthest bichromatic pairs for points in the plane
• New lower bounds for halfspace emptiness
• Computing and verifying depth orders
• Algorithms for ham-sandwich cuts
• Ray shooting and lines in space
• Algorithmic Geometry
• Low-cost fault-tolerant spanning graphs for point sets in the Euclidean plane
• Lower Bounds for Fundamental Geometric Problems
• Computing the smallest $k$-enclosing circle and related problems
• A cell-probe lower bound for dynamic nearest-neighbor searching
• Geometric algorithms for density-based data clustering
• Minimum weight Euclidean matching and weighted relative neighborhood graphs
• Quality of EDA CAD tools: definitions, metrics and directions
• Kinetic Maintenance of Proximity Structures