Paper by Erik D. Demaine
- 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 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.
- 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.
These pages are generated automagically from a
BibTeX file.
Last updated March 12, 2024 by
Erik Demaine.