Maintaining range trees in secondary memory. Part I: partitions

M.H. Overmars, M.H.M. Smid, M. Berg, de, M.J. Kreveld, van

    Research output: Contribution to journalArticleAcademicpeer-review

    9 Citations (Scopus)


    Range trees are used for solving the orthogonal range searching problem, a problem that has applications in e.g. databases and computer graphics. We study the problem of storing range trees in secondary memory. To this end, we partition range trees into parts that are stored in consecutive blocks in secondary memory. This paper gives a number of partition schemes that limit the part-sizes and the number of disk accesses necessary to perform updates and queries. We show e.g., that for each fixed positive integer k, there is a partition of a two-dimensional range tree into parts of size O(n 1/k ), such that each update requires at most k(2k+1) disk accesses, and each query requires at most 8k 2+2k+2t disk accesses, where t is the number of answers to the range query.
    Original languageEnglish
    Pages (from-to)423-452
    Number of pages30
    JournalActa Informatica
    Issue number5
    Publication statusPublished - 1989


    Dive into the research topics of 'Maintaining range trees in secondary memory. Part I: partitions'. Together they form a unique fingerprint.

    Cite this