Space-time tradeoffs for emptiness queries

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 Broennimann, 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 = Ω((n/log n)^d-(d-1)/(d+1). Using different techniques, we show that Ω(n^d/d/polylog n) preprocessing time is required to achieve polylogarithmic query time, and that Ω(n^(d-1)/d/polylog n) query time is required if only O(n polylog n) preprocessing time is used. These two lower bounds are optimal up to polylogarithmic factors. For two-dimensional queries, we obtain an optimal continuous tradeoff between these two extremes. Finally, using a reduction argument, we show that the same lower bounds hold for halfspace emptiness queries in IR^d(d+3)/2 on a restricted class of partition graphs.