New Lower Bounds for Halfspace Emptiness

We derive a lower bound of\Omega n 4=3 ) for the halfspace emptiness problem: Given a set of n points and n hyperplanes in IR 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 of \Omega n log n). The lower bound applies to partitioning algorithms in which every query region is a polyhedron with a constant number of facets. 1. Introduction The halfspace emptiness problem asks, given a set of points and a set of halfspaces, whether any halfspace contains a point. In this paper, we derivenewlower bounds for the time required to solve this problem, generalizing earlier lower bounds for Hopcroft's pointline incidence problem [16]. In this paper, we will consider the following formulation of the problem: Given a set of points and hyperplanes, is every pointaboveevery hyperplane? Using linear programming [13, 21, 24, 25], we can decide in linear time whether the union of a s..