Randomized multidimensional search trees: lazy balancing and dynamic shuffling
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 180-196
- https://doi.org/10.1109/sfcs.1991.185368
Abstract
A randomized technique, called dynamic shuffling, is given for multidimensional dynamic search. This technique, when specialized to the problem of searching in sorted lists, yields the previously known randomized binary trees (treaps). The crux of the technique is a multidimensional generalization of the rotation operation on binary search trees. Simultaneously, it is shown how to dynamize the randomized incremental algorithms so as to allow additions as well as deletions of objects. The techniques are based on remembering the history of the actual or imaginary sequence of updates. The techniques are applied to several problems in computational geometry.Keywords
This publication has 16 references indexed in Scilit:
- Randomized multidimensional search trees: further results in dynamic samplingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On levels in arrangements and voronoi diagramsDiscrete & Computational Geometry, 1991
- Dynamic point location in arrangements of hyperplanesPublished by Association for Computing Machinery (ACM) ,1991
- A deterministic view of random sampling and its use in geometryCombinatorica, 1990
- Applications of random sampling in computational geometry, IIDiscrete & Computational Geometry, 1989
- An efficient algorithm for hidden surface removalPublished by Association for Computing Machinery (ACM) ,1989
- A fast planar partition algorithm. IPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Voronoi diagrams and arrangementsDiscrete & Computational Geometry, 1986
- On k-Nearest Neighbor Voronoi Diagrams in the PlaneIEEE Transactions on Computers, 1982
- Decomposable searching problems I. Static-to-dynamic transformationJournal of Algorithms, 1980