| Abstract On the Complexity of Halfspace Volume Queries (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Given a polyhedron P in R d with n vertices, a halfspace volume query asks for the volume of P ∩ H for a given halfspace H. We show that, for d ≥ 3, such queries can require Ω(n) operations even if the polyhedron P is convex and can be preprocessed arbitrarily. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||