Orthogonal range searching on the RAM, revisited
Orthogonal range searching on the RAM, revisited
We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model: We present two data structures for 2-d orthogonal range emptiness. The first achieves O(n lg lg n) space and …