Lower Bounds for Orthogonal Range Searching: I. The Reporting Case

We establish lower bounds on the complexity of orthogonal range reporting in the static case. Given a collection of n points in d-space and a box [a₁, b₁] X … X [a_d, b_d], report every point whose ith coordinate lies in [a_i, b_i], for each i = l, …, d. The collection of points is fixed once and for all and can be preprocessed. The box, on the other hand, constitutes a query that must be answered online. It is shown that on a pointer machine a query time of O1990), where k is the number of points to be reported, can only be achieved at the expense of Ω(n(log n/log log n)^d-1) storage. Interestingly, these bounds are optimal in the pointer machine model, but they can be improved (ever so slightly) on a random access machine. In a companion paper, we address the related problem of adding up weights assigned to the points in the query box.