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 ofOmega(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.