Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 472-481 |
| Number of pages | 10 |
| Journal | Annual Symposium on Foundations of Computer Science - Proceedings |
| State | Published - Dec 1 1996 |
| Externally published | Yes |
| Event | Proceedings of the 1996 37th Annual Symposium on Foundations of Computer Science - Burlington, VT, USA Duration: Oct 14 1996 → Oct 16 1996 |
ASJC Scopus subject areas
- Hardware and Architecture