HOW HARD IS HALF-SPACE RANGE SEARCHING

We investigate the complexity of half-space range searching: given n p oints in d-space, build a data structure that allows us to determine e fficiently how many points lie in a query half-space. We establish a t radeoff between the storage m and the worst-case query time t in the F redman/Yao arithmetic model of computation. We show that t must be at least on the order of (n/log n)1-(d-1)/d(d+1) / m1/d. Although the bou nd is unlikely to be optimal, it falls reasonably close to the recent upper bound of O(n/m1/d) established by Matousek. We also show that it is possible to devise a sequence of n inserts and half-space range qu eries that require a total time of n2-O(1/d). Our results imply the fi rst nontrivial lower bounds for spherical range searching in any fixed dimension. For example, they show that, with linear storage, circular range queries in the plane require OMEGA(n1/3) time (modulo a logarit hmic factor).