On the complexity of halfsapce volume queries

Written with Erik D. Demaine and Stefan Langerman
Proceedings of the 15th Canadian Conference on Computational Geometry, 159-160, 2003.

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.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 04 Dec 2003