Box-trees and R-trees with near-optimal query time

PK Agarwal, M de Berg, J Gudmundsson, Mikael Hammar, HJ Haverkort

    Research output: Contribution to journalArticlepeer-review

    Abstract

    A box-tree is a bounding-volume hierarchy that uses axis-aligned boxes as bounding volumes. The query complexity of a box-tree with respect to a given type of query is the maximum number of nodes visited when answering such a query. We describe several new algorithms for constructing box-trees with small worst-case query complexity with respect to queries with axis-parallel boxes and with points. We also prove lower bounds on the Worst-case query complexity for box-trees, which show that our results are optimal or close to optimal. Finally, we present algorithms to convert box-trees to R-trees, resulting in R-trees with (almost) optimal query complexity.
    Original languageEnglish
    Pages (from-to)291-312
    JournalDiscrete & Computational Geometry
    Volume28
    Issue number3
    DOIs
    Publication statusPublished - 2002

    Subject classification (UKÄ)

    • Computer Science

    Fingerprint

    Dive into the research topics of 'Box-trees and R-trees with near-optimal query time'. Together they form a unique fingerprint.

    Cite this