LOWER BOUNDS FOR OFF-LINE RANGE SEARCHING

This paper proves three lower bounds for variants of the following ran ge-searching problem: Given n weighted points in R(d) and n axis-paral lel boxes, compute the sum of the weights within each box: (1) if both additions and subtractions are allowed, we prove that Omega (n log lo g n) is a lower bound on the number of arithmetic operations; (2) if s ubtractions are disallowed the lower bound becomes Omega (n(log n/log log n)(d-1)), which is nearly optimal; (3) finally, for the case where boxes are replaced by simplices, we establish a quasi-optimal lower b ound of Omega (n(2-2/(d+1)))/polylog(n).