New lower bounds for halfspace emptiness

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 of n points and n hyperplanes in R⁵, is every point above every hyperplane? This matches the best known upper bound to within polylogarithmic factors, and improves the previous best lower bound of Omega(n log n). Our lower bound applies to a general class of geometric divide-and-conquer algorithms, called 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