Paper by Erik D. Demaine

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.

Given a polyhedron P in Rd 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.

The paper is 2 pages.

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.
These pages are generated automagically from a BibTeX file.
Last updated May 17, 2017 by Erik Demaine.