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

P.K. Agarwal, M. Berg, de, J. Gudmundsson, M. Hammar, H.J. Haverkort

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    38 Citaten (Scopus)


    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.
    Originele taal-2Engels
    Pagina's (van-tot)291-312
    TijdschriftDiscrete and Computational Geometry
    Nummer van het tijdschrift3
    StatusGepubliceerd - 2002


    Duik in de onderzoeksthema's van 'Box-trees and R-trees with near-optimal query time'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit