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)

    Abstract

    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
    PublisherSpringer
    Pages167-178
    ISBN (Print)3-540-41004-X
    DOIs
    Publication statusPublished - 2000

    Publication series

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

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

    Cite this