On R-trees with low stabbing number

M. Berg, de, J. Gudmundsson, M. Hammar, M.H. Overmars

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    9 Citations (Scopus)


    The R-tree is a well-known bounding-volume hierarchy that is suitable for storing geometric data on secondary memory. Unfortunately, no good analysis of its query time exists. We describe a new algorithm to construct an R-tree for a set of planar objects that has provably good query complexity for point location queries and range queries with ranges of small width. For certain important special cases, our bounds are optimal. We also show how to update the structure dynamically, and we generalize our results to higher-dimensional spaces.
    Original languageEnglish
    Title of host publicationAlgorithms - ESA 2000 : 8th annual european symposium, Saarbrücken, Germany, September 5-8, 2000 : proceedings
    EditorsM.S. Paterson
    Place of PublicationBerlin
    ISBN (Print)3-540-41004-X
    Publication statusPublished - 2000

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'On R-trees with low stabbing number'. Together they form a unique fingerprint.

    Cite this