New lower bounds for halfspace emptiness

Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 472-481, 1996.

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


Abstract:
We present a lower bound of Omega(n4/3) for the following halfspace emptiness problem: Given a set of n points and n hyperplanes in R5, 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