2009.12.07 | Else Magård

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

Speaker: Kostas Tsakalidis, Aarhus University

Abstract:

We consider the problem of maintaining dynamically a set of points in the plane and supporting range queries of the type $[a,b]\\times(- \\infty, c]$. We assume that the inserted points have their x-coordinates drawn from a class of {\\em 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.

Joint work with: G.S. Brodal, A. Kaporis, S. Sioutas, K. Tsichlas

Host: Gerth Stølting Brodal