Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time

Gerth Stølting Brodal, Alexis C. Kaporis, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas

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.

Abstract

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

10.1007/978-3-642-10631-6_21

Links

BIBTEX entry

@incollection{isaac09range,
  author = "Gerth St{\o}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"
}