Proceedings of the 15th Canadian Conference on Computational Geometry, 159-160, 2003.

Abstract:

For any polyhedronPinR^{d}withnvertices, a halfspace volume query asks for the volume of its intersection with a given halfspace. We show that, ford≥3, such queries can require Ω(n) operations even if the polyhedronPis convex and can be preprocessed arbitrarily.

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