Volume queries in polyhedra

John Iacono; Stefan Langcrman

doi:10.1007/3-540-47738-1_13

Volume queries in polyhedra

John Iacono, Stefan Langcrman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We present a simple and practical data structure for storing a (not necessarily convex) polyhedron P which can, given a query surface S cutting the polyhedron, determine the volume and the area of the portion of the polyhedron above S. The queries are answered in a time linear in the size (complexity) of S. The space and preprocessing time for this data structure are linear in the size of P. We also present an intermediary data structure for planar graphs which is of use in other application domains.

Original language	English (US)
Title of host publication	Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers
Editors	Jin Akiyama, Mikio Kano, Masatsugu Urabe
Publisher	Springer Verlag
Pages	156-159
Number of pages	4
ISBN (Print)	9783540477389
DOIs	https://doi.org/10.1007/3-540-47738-1_13
State	Published - 2001
Event	Japanese Conference on Discrete and Computational Geometry, JCDCG 2000 - Tokyo, Japan Duration: Nov 22 2000 → Nov 25 2000

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2098
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	Japanese Conference on Discrete and Computational Geometry, JCDCG 2000
Country/Territory	Japan
City	Tokyo
Period	11/22/00 → 11/25/00

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-47738-1_13

Cite this

Iacono, J., & Langcrman, S. (2001). Volume queries in polyhedra. In J. Akiyama, M. Kano, & M. Urabe (Eds.), Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers (pp. 156-159). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2098). Springer Verlag. https://doi.org/10.1007/3-540-47738-1_13

Volume queries in polyhedra. / Iacono, John; Langcrman, Stefan.
Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers. ed. / Jin Akiyama; Mikio Kano; Masatsugu Urabe. Springer Verlag, 2001. p. 156-159 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2098).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Iacono, J & Langcrman, S 2001, Volume queries in polyhedra. in J Akiyama, M Kano & M Urabe (eds), Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2098, Springer Verlag, pp. 156-159, Japanese Conference on Discrete and Computational Geometry, JCDCG 2000, Tokyo, Japan, 11/22/00. https://doi.org/10.1007/3-540-47738-1_13

Iacono J, Langcrman S. Volume queries in polyhedra. In Akiyama J, Kano M, Urabe M, editors, Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers. Springer Verlag. 2001. p. 156-159. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-47738-1_13

Iacono, John ; Langcrman, Stefan. / Volume queries in polyhedra. Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers. editor / Jin Akiyama ; Mikio Kano ; Masatsugu Urabe. Springer Verlag, 2001. pp. 156-159 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{787726ea3fd84ebba17236f1f62bde52,

title = "Volume queries in polyhedra",

abstract = "We present a simple and practical data structure for storing a (not necessarily convex) polyhedron P which can, given a query surface S cutting the polyhedron, determine the volume and the area of the portion of the polyhedron above S. The queries are answered in a time linear in the size (complexity) of S. The space and preprocessing time for this data structure are linear in the size of P. We also present an intermediary data structure for planar graphs which is of use in other application domains.",

author = "John Iacono and Stefan Langcrman",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; Japanese Conference on Discrete and Computational Geometry, JCDCG 2000 ; Conference date: 22-11-2000 Through 25-11-2000",

year = "2001",

doi = "10.1007/3-540-47738-1_13",

language = "English (US)",

isbn = "9783540477389",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "156--159",

editor = "Jin Akiyama and Mikio Kano and Masatsugu Urabe",

booktitle = "Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers",

}

TY - GEN

T1 - Volume queries in polyhedra

AU - Iacono, John

AU - Langcrman, Stefan

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - We present a simple and practical data structure for storing a (not necessarily convex) polyhedron P which can, given a query surface S cutting the polyhedron, determine the volume and the area of the portion of the polyhedron above S. The queries are answered in a time linear in the size (complexity) of S. The space and preprocessing time for this data structure are linear in the size of P. We also present an intermediary data structure for planar graphs which is of use in other application domains.

AB - We present a simple and practical data structure for storing a (not necessarily convex) polyhedron P which can, given a query surface S cutting the polyhedron, determine the volume and the area of the portion of the polyhedron above S. The queries are answered in a time linear in the size (complexity) of S. The space and preprocessing time for this data structure are linear in the size of P. We also present an intermediary data structure for planar graphs which is of use in other application domains.

UR - http://www.scopus.com/inward/record.url?scp=84974695543&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84974695543&partnerID=8YFLogxK

U2 - 10.1007/3-540-47738-1_13

DO - 10.1007/3-540-47738-1_13

M3 - Conference contribution

AN - SCOPUS:84974695543

SN - 9783540477389

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 156

EP - 159

BT - Discrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers

A2 - Akiyama, Jin

A2 - Kano, Mikio

A2 - Urabe, Masatsugu

PB - Springer Verlag

T2 - Japanese Conference on Discrete and Computational Geometry, JCDCG 2000

Y2 - 22 November 2000 through 25 November 2000

ER -

Volume queries in polyhedra

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this