We 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 can not 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 Omega(log n / log T(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).
Full paper (postscript)
Full paper (pdf)