Dynamic half-space reporting, geometric optimization, and minimum spanning trees. (English) Zbl 0977.68567
33rd annual symposium on Foundations of computer science (FOCS). Proceedings, Pittsburgh, PA, USA, October 24-27, 1992. Washington, DC: IEEE Computer Society Press, 80-89 (1992).
Summary: We descibe dynamic data structures for half-space range reporting and for maintaining the minima of a decomposable function. Using these data structures, we obtain efficient dynamic algorithms for a number of geometric problems, including closest/farthest neighbor searching, fixed dimension linear programing, bi-chromatic closest pair, diameter, and Euclidean minimum spanning tree.
|68U05||Computer graphics; computational geometry|