On the difficulty of range searching

AbstractWe consider the general problem of (2-dimensional) range reporting allowing arbitrarily convex queries. We show that using a traditional approach, even when incorporating techniques like those used in fusion trees, a polylogarithmic query time cannot be achieved unless more than linear space is used. Our arguments are based on a new non-trivial lower bound in a model of computation which, in contrast to the pointer machine model, allows for the use of arrays and bit manipulation. The crucial property of our model, Layered partitions, is that it can be used to describe all known algorithms for processing range queries, as well as many other data structures used to represent multi-dimensional data. We show that Ω(lognlogT(n)) partitions must be used to allow queries in O(T(n) + k) time, for n total and k reported elements, and for any growing function T(n)