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 Matous&caron;ek. 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-&thgr;(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 &OHgr;( n 1/3 ) time (modulo a logarithmic factor).
complexity point data structures query storage timing model of computation order log knowledge lower bound optimality sequence range queries examples factor space case