LOWER BOUNDS FOR ORTHOGONAL RANGE SEARCHING .1. 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 [a1, b1] X … X [ad, bd], report every point whose ith coordinate lies in [ai, bi], 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. © 1990, ACM. All rights reserved.