Dynamic half-space reporting, geometric optimization, and minimum spanning trees
Pankaj K. Agarwal, David Eppstein, Jiřı́ Matoušek · 1992
The authors describe dynamic data structures for half-space range reporting and for maintaining the minima of a decomposable function. Using these data structures, they obtain efficient dynamic algorithms for a number of geometric problems, including closest/farthest neighbor searching, fixed dimension linear programming, bi-chromatic closest pair, diameter, and Euclidean minimum spanning tree.>