**Reference**:- Erik D. Demaine, Jeff Erickson, and Stefan Langerman, “On the Complexity of Halfspace Volume Queries”, in
*Proceedings of the 15th Canadian Conference on Computational Geometry (CCCG 2003)*, Halifax, Nova Scotia, Canada, August 11–13, 2003, pages 159–160. **Abstract**:-
Given a polyhedron
*P*in**R**^{d}with*n*vertices, a halfspace volume query asks for the volume of*P*intersect*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. **Length**:- The paper is 2 pages.
**Availability**:- The paper is available in PostScript (96k), gzipped PostScript (40k), and PDF (80k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated September 3, 2017 by Erik Demaine.