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.

BibTeX

@InProceedings{VolumeQueries_CCCG2003,
  AUTHOR        = {Erik D. Demaine and Jeff Erickson and Stefan Langerman},
  TITLE         = {On the Complexity of Halfspace Volume Queries},
  BOOKTITLE     = {Proceedings of the 15th Canadian Conference on Computational
                   Geometry (CCCG 2003)},
  bookurl       = {http://www.cs.dal.ca/~cccg/},
  ADDRESS       = {Halifax, Nova Scotia, Canada},
  MONTH         = {August 11--13},
  YEAR          = 2003,
  PAGES         = {159--160},

  length        = {2 pages},
  unrefereed    = 1,
  dblp          = {https://dblp.org/rec/conf/cccg/DemaineEL03},
  ee            = {http://www.cccg.ca/proceedings/2003/35.pdf},
}

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]