Space-time tradeoffs or emptiness queries

We develop the rst nontrivial lower bounds on the complexity of online hype rplane and halfspace emptiness queries. Our lower bounds apply to a general class of geometric range query data structures called partition graphs. In formally, a partition graph is a directed acyclic graph that describes a re cursive decomposition of space. We show that any partition graph that suppo rts hyperplane emptiness queries implicitly defines a halfspace range query data structure in the Fredman/Yao semigroup arithmetic model, with the sam e asymptotic space and time bounds. Thus, results of Bronnimann, Chazelle, and Pach imply that any partition graph of size s that supports hyperplane emptiness queries in time t satisfies the inequality st(d) = Omega((n/log n )(d-(d-1)/(d+1))). Using different techniques, we improve previous lower bo unds for Hopcroft's problem Given a set of points and hyperplanes, does any hyperplane contain a point?-in dimensions four and higher. Using this offl ine result, we show that for online hyperplane emptiness queries, Omega(n(d )/polylog n) space is required to achieve polylogarithmic query time, and O mega(n((d-1)/d)/polylog n) query time is required if only O(n polylog n) sp ace is available. These two lower bounds are optimal up to polylogarithmic factors. For two-dimensional queries, we obtain an optimal continuous trade off st(2) = Omega(n(2)) between these two extremes. Finally, using a liftin g argument, we show that the same lower bounds hold for both offline and on line halfspace emptiness queries in Rd(d+3)/2.