Ray shooting and intersection searching amidst fat convex polyhedra in 3-space

Boris Aronov, Mark De Berg, Chris Gray

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in ℝ3. The data structure uses O(n2+ε) storage and preprocessing time, and queries can be answered in O(log2 n) time. A trade-off between storage and query time is also possible: for any m with n < m < n2, we can construct a structure that uses O(m1+ε) storage and preprocessing time such that queries take O((n/√m) log2 n) time. We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in ℝ3. For any m with n< m < n2, we can construct a structure that uses O(m1+ε) storage and preprocessing time such that all polyhedra intersecting a query simplex can be reported in O((n/m1/3) log n + k) time, where k is the number of answers.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Twenty-Second Annual Symposium on Computational Geometry 2006, SCG'06
    PublisherAssociation for Computing Machinery (ACM)
    Pages88-94
    Number of pages7
    ISBN (Print)1595933409, 9781595933409
    DOIs
    StatePublished - 2006
    Event22nd Annual Symposium on Computational Geometry 2006, SCG'06 - Sedona, AZ, United States
    Duration: Jun 5 2006Jun 7 2006

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry
    Volume2006

    Other

    Other22nd Annual Symposium on Computational Geometry 2006, SCG'06
    CountryUnited States
    CitySedona, AZ
    Period6/5/066/7/06

    Keywords

    • Computational geometry
    • Fat objects
    • Intersection searching
    • Ray shooting

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics

    Fingerprint Dive into the research topics of 'Ray shooting and intersection searching amidst fat convex polyhedra in 3-space'. Together they form a unique fingerprint.

    Cite this