Dynamic Planar Orthogonal 3-sided Range Reporting in Expected Doubly
Logarithmic Time

by Konstantinos Tsakalidis

We consider the problem of maintaining dynamically a set of points in the
plane and supporting 3-sided orthogonal range queries (namely, of the type
[a,b](-$\infinity$,c]). All previous results in the Pointer Machine, the RAM 
and the I/O model, achieve nearly logarithmic worst case query and update time
using linear space. By assuming that the input coordinates are drawn from
various probabilistic distributions, we show how to decrease these
complexities to expected doubly logarithmic.

Let $n$ be the number of points currently stored in the data structure,
let $t$ be the number of reported points and $B$ the size of a block in
external memory. We first reduce the amortized update time to 
$O(\log\log n)$ in the RAM, when both x and y-coordinates are drawn from an 
unknown continuous \emph{$\mu$-random distribution}. Respectively, in the 
I/O model we achieve $O(\log_B \log n)$ amortized update I/Os. Next, we
additionally reduce the query time to $O(\log\log n)$, when the
x-coordinates are drawn from the \emph{Zipfian} distribution. In the I/O
model we achieve $O(\log_B \log n + t/B)$ query I/Os, by moreover imposing
the y-coordinates to be \emph{smoothly} distributed. So far all improved
complexities are expected with high probability. 

Independently, we show how to achieve $O(\log \log n + t)$ expected with
high probability query time and $O(\log \log n)$ expected amortized update
time, in the RAM, by only assuming that the x-coordinates are smoothly
distributed. In the I/O model, the same assumption leads to 
$O(\log \log_B n + t/B)$ expected with high probability query I/Os and 
$O(\log_B \log n)$ expected amortized update I/Os. 

Joint work with Gerth Brodal, Alexis Kaporis, Apostolos Papadopoulos, 
Spyros Sioutas and Kostas Tsichlas