New lower bounds for halfspace emptiness

Research output: Contribution to journalConference articlepeer-review


We derive a lower bound of Ω(n4/3) for the half-space emptiness problem: Given a set of n points and n hyperplanes in IR5, 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 Ω(n log n). The lower bound applies to partitioning algorithms in which every query region is a polyhedron with a constant number of facets.

Original languageEnglish (US)
Pages (from-to)472-481
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Dec 1 1996
Externally publishedYes
EventProceedings of the 1996 37th Annual Symposium on Foundations of Computer Science - Burlington, VT, USA
Duration: Oct 14 1996Oct 16 1996

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this