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

Boris Aronov, Mark De Berg, Chris Gray

    Research output: Contribution to journalArticle

    Abstract

    We present a data structure for ray-shooting queries in a set of convex fat polyhedra of total complexity n in R3. The data structure uses O(n2 +) storage and preprocessing time, and queries can be answered in O( log2n) 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) log2n) time. We also describe a data structure for simplex intersection queries in a set of n convex fat constant-complexity polyhedra in R3. For any m with n<m< n3, 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)logn+k) time, where k is the number of answers.

    Original languageEnglish (US)
    Pages (from-to)68-76
    Number of pages9
    JournalComputational Geometry: Theory and Applications
    Volume41
    Issue number1-2
    DOIs
    StatePublished - Oct 2008

    Keywords

    • Fat objects
    • Geometric data structures
    • Intersection searching
    • Ray shooting

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • 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