In Proc. 20th Annual International Symposium on Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science, pages 193-202. Springer Verlag, Berlin, 2009.
We consider the problem of maintaining dynamically a set of points in the plane and supporting range queries of the type [a,b]x(- ∞, c]. We assume that the inserted points have their x-coordinates drawn from a class of smooth distributions, whereas the y-coordinates are arbitrarily distributed. The points to be deleted are selected uniformly at random among the inserted points. For the RAM model, we present a linear space data structure that supports queries in O(log log n + t) expected time with high probability and updates in O(log log n) expected amortized time, where n is the number of points stored and t is the size of the output of the query. For the I/O model we support queries in O(log logB n + t/B) expected I/Os with high probability and updates in O(logB log n) expected amortized I/Os using linear space, where B is the disk block size. The data structures are deterministic and the expectation is with respect to the input distribution.
Copyright notice© Springer-Verlag Berlin Heidelberg 2009. All rights reserved.
Online version
isaac09range.pdf (176 Kb)
DOI
Links
BIBTEX entry
@incollection{isaac09range,
author = "Gerth Stølting Brodal and Alexis C. Kaporis and Spyros Sioutas and Konstantinos Tsakalidis and Kostas Tsichlas",
booktitle = "Proc. 20th Annual International Symposium on Algorithms and Computation",
doi = "10.1007/978-3-642-10631-6_21",
isbn = "978-3-642-10630-9",
pages = "193-202",
publisher = "Springer {V}erlag, Berlin",
series = "Lecture Notes in Computer Science",
title = "Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time",
volume = "5878",
year = "2009"
}
Other versions