Merged into the journal version of "Space-time tradeoffs for emptiness queries".

- Download FOCS version (© 1996 IEEE)
- References and BibTeX entry of FOCS version, from HBP. (Please note that the title is incorrect!)

Abstract:

We present a lower bound of Omega(n^{4/3}) for the following halfspace emptiness problem: Given a set ofnpoints andnhyperplanes inR^{5}, is every point above every hyperplane? This matches the best known upper bound to within polylogarithmic factors, and improves the previous best lower bound ofOmega( . Our lower bound applies to a general class of geometric divide-and-conquer algorithms, callednlogn)polyhedral partitioning algorithms. Informally, a polyhedral partitioning algorithm covers space with a constant number of constant-complexity polyhedra, determines for each polyhedron which points and halfspaces intersect it, and recursively solves the resulting subproblems.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Nov 1999