caa a22 4500 467989915 CHVBK 20180323112541.0 cr unu---uuuuu 170328e19900401xx s 000 0 eng 10.1007/BF00289018 doi (NATIONALLICENCE)springer-10.1007/BF00289018 Maintaining range trees in secondary memory [Elektronische Daten] Part I: Partitions [Mark Overmars, Michiel Smid, Mark de Berg, Marc van Kreveld] Summary: 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. Springer-Verlag, 1990 Overmars Mark Department of Computer Science, University of Utrecht, P.O. Box 80089, NL-3508, TB Utrecht, The Netherlands aut Smid Michiel Departments of Mathematics and Computer Science, University of Amsterdam, Plantage Muidergracht 24, NL-1018, TV Amsterdam, The Netherlands aut de Berg Mark Department of Computer Science, University of Utrecht, P.O. Box 80089, NL-3508, TB Utrecht, The Netherlands aut van Kreveld Marc Department of Computer Science, University of Utrecht, P.O. Box 80089, NL-3508, TB Utrecht, The Netherlands aut Acta Informatica Springer-Verlag 27/5(1990-04-01), 423-452 0001-5903 27:5<423 1990 27 236 https://doi.org/10.1007/BF00289018 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00289018 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Overmars Mark Department of Computer Science, University of Utrecht, P.O. Box 80089, NL-3508, TB Utrecht, The Netherlands aut NATIONALLICENCE 700 1- Smid Michiel Departments of Mathematics and Computer Science, University of Amsterdam, Plantage Muidergracht 24, NL-1018, TV Amsterdam, The Netherlands aut NATIONALLICENCE 700 1- de Berg Mark Department of Computer Science, University of Utrecht, P.O. Box 80089, NL-3508, TB Utrecht, The Netherlands aut NATIONALLICENCE 700 1- van Kreveld Marc Department of Computer Science, University of Utrecht, P.O. Box 80089, NL-3508, TB Utrecht, The Netherlands aut NATIONALLICENCE 773 0- Acta Informatica Springer-Verlag 27/5(1990-04-01), 423-452 0001-5903 27:5<423 1990 27 236 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer