Dynamic half-space reporting, geometric optimization, and minimum spanning trees
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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.<>Keywords
This publication has 24 references indexed in Scilit:
- Maintaining the minimal distance of a point set in polylogarithmic timeDiscrete & Computational Geometry, 1992
- Efficient Point Location in a Convex Spatial Cell-ComplexSIAM Journal on Computing, 1992
- Maintenance of geometric extremaJournal of the ACM, 1991
- Quasi-optimal upper bounds for simplex range searching and new zone theoremsPublished by Association for Computing Machinery (ACM) ,1990
- Geometry Helps in MatchingSIAM Journal on Computing, 1989
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- A Randomized Algorithm for Closest-Point QueriesSIAM Journal on Computing, 1988
- New applications of random sampling in computational geometryDiscrete & Computational Geometry, 1987
- Planar point location using persistent search treesCommunications of the ACM, 1986
- Batched dynamic solutions to decomposable searching problemsJournal of Algorithms, 1985