Multidimensional Range Selection

摘要

We study the problem of supporting (orthogonal) range selection queries over a set of n points in constant-dimensional space. Under the standard word-RAM model with word size w = Ω(lg n), we present data structures that occupy O(n · (lg n/lg lg n)~(d-1)) words of space and support d-dimensional range selection queries using O((lg n/lg lg n)~d) query time. This improves the best known data structure by a factor of lg lg n in query time. To develop our data structures, we generalize the "parallel counting" technique of Brodal, Gfeller, Jorgensen, and Sanders (2011) for one-dimensional range selection to higher dimensions. As a byproduct, we design data structures to support d-dimensional range counting queries within O(n · (lg n/lg w + 1)~(d-2)) words of space and O((lg n/lg w + 1)~(d-1)) query time, for any word size w = Ω(lg n). This improves the best known result of JaJa, Mortensen, and Shi (2004) when lg w lg lg n.