Dynamic half-space reporting, geometric optimization, and minimum spanning trees
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.
Agarwal, PK; Eppstein, D; Matousek, J
Volume / Issue
Start / End Page
International Standard Serial Number (ISSN)
International Standard Book Number 10 (ISBN-10)
Digital Object Identifier (DOI)