Space­time tradeoffs for emptiness queries

Proceedings of the 13th Annual ACM Symposium on Computational Geometry, 304-313, 1997.

The journal version includes results from "New lower bounds for halfspace emptiness".

• Download journal version (final except for copy-editing, © 2000 SIAM):
• Official journal version from SIAM (subscription required)

• Download SoCG version (© 1997 ACM):
• Official SoCG version from ACM's Digital Library (subscription or $5 payment required)

• Recent improvements

Abstract:
We present the first nontrivial space­time tradeoff lower bounds for hyperplane and halfspace emptiness range 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 searching data structure in the Fredman/Yao semigroup arithmetic model with the same time and space bounds. Thus, results of Brönnimann, 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 improve previous lower bounds for Hopcroft's problem -- Given a set of points and hyperplanes, does any hyperplane contain a point? -- in dimensions four and higher. Using this offline result, we show that for online hyperplane emptiness queries, Omega(n^d/polylog n) space and preprocessing time is required to acheive polylogarithmic query time, and that Omega(n^1-1/d polylog n) query time is required if only O(n polylog n) space is available. 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 lifting argument, we show that the same lower bounds hold for offline and online halfspace emptiness queries in R^d(d+3)/2.

Update (26 Sep 2000): Braß and Knauer, using recent work of Bárány, Harcos, Pach, and Tardos, recently discovered a set of n points and m hyperplanes, where at most d hyperplanes pass through any point, with a large number of point-hyperplane incidences. Their construction immediately improves several of my lower bounds in d>2 dimensions. For Hopcroft's problem, we have the new lower bound Omega(n log m + nd/(2d-1) m(2d-2)/(2d-1) + n(2d-2)/(2d-1) md/(2d-1) + m log n). This is an improvement for all n1/d << m << nd. For online hyperplane emptiness queries, we have new space-time tradeoffs st2d-2 = Omega(nd) and std/(d+1) = Omega(n2), and the analagous preprocessing-query tradeoffs. This is an improvement for all n << s << nd. There are similar improvements for offline and online halfspace emptiness queries in dimensions nine and higher. All these improvements follow directly from the techniques in my paper. Imre Bárány, Gergely Harcos, János Pach, and Gábor Tardos. Covering lattice points by subspaces. To appear in Period. Math. Hung. Peter Braß and Christian Knauer. Fast enumeration of point-hyperplane incidences. Technischer Bericht B 00-13, Freie Universität Berlin, Fachbereich Mathematik und Informatik, 2000.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 14 Feb 2002