Space-time tradeoffs for emptiness queries (extended abstract)
Jeff Erickson · 1997
We present the first nontrivial space-time tradeoff lower bounds for hyperplane and halfspace emptiness queries. Our lower bounds apply to a general class of geometric range query data structures called partition graphs. Informally, a partition graph is a directed acyclic graph that describes a recursive decomposition of space. We show that any partition graph that supports hyperplane emptiness queries implicitly defines a halfspace range query data structure in the Fredman/Yao semigroup arithmetic model, with the same 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 must satisfy the inequality st d =\\Omega ((n= log n) d-(d-1)=(d+1) ). Using different techniques, we show that\\Omega (n d = polylog n) preprocessing time is required to achieve polylogarithmic query time, and that\\Omega (n (d-1)=d = polylog n) query time is required if only O(npolylog n) preproce...