Volume queries in polyhedra

John Iacono, Stefan Langcrman

    Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
    Title of host publicationDiscrete and Computational Geometry - Japanese Conference, JCDCG 2000, Revised Papers
    EditorsJin Akiyama, Mikio Kano, Masatsugu Urabe
    PublisherSpringer Verlag
    Pages156-159
    Number of pages4
    ISBN (Print)9783540477389
    DOIs
    StatePublished - 2001
    EventJapanese Conference on Discrete and Computational Geometry, JCDCG 2000 - Tokyo, Japan
    Duration: Nov 22 2000Nov 25 2000

    Publication series

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

    Other

    OtherJapanese Conference on Discrete and Computational Geometry, JCDCG 2000
    CountryJapan
    CityTokyo
    Period11/22/0011/25/00

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Volume queries in polyhedra'. Together they form a unique fingerprint.

    Cite this