How hard is halfspace range searching

We investigate the complexity of halfspace range searching: Given n points in d-space, build a data structure that allows us to determine efficiently how many points lie in a query halfspace. We establish a tradeoff between the storage m and the worst-case query time t in the Fredman/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)} /m^1/d To our knowledge, this is the first nontrivial lower bound for halfspace range searching. Although the bound is unlikely to be optimal, it falls reasonably close to the recent O(n(log m/n)^d+1/m^1/d upper bound established by Matousek. We also show that it is possible to devise a sequence of n inserts and halfspace range queries that require a total time of n^2-Θ(1/d). Our results imply 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 Ω(n^1/3) time (modulo a logarithmic factor).