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

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
log_{B} *n* + *t*/*B*) expected I/Os with high probability and updates in
*O*(log_{B} 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**

**BIBT**_{E}X 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"
}