Abstract:
For any polyhedron P in Rd with n vertices, a halfspace volume query asks for the volume of its intersection with a given halfspace. We show that, for d≥3, such queries can require Ω(n) operations even if the polyhedron P is convex and can be preprocessed arbitrarily.