# Dynamic Orthogonal Range Searching on the RAM, Revisited

## Konstantinos Tsakalidis, NYU/Tandon

## September 26, 2017

## Room WWH312 (note unusual room!!!)

We study a longstanding problem in computational geometry: 2-d dynamic
orthogonal range reporting. We present a new data structure achieving
$O(\log n/\log \log n + k)$ optimal query time and $O(\log^{2/3+o(1)} n)$
update time (amortized) in the word RAM model, where $n$ is the number
of data points and $k$ is the output size. This is the first improvement
in over 10 years of Mortensenâ€™s previous result [SIAM J. Comput., 2006], which has $O(\log^{7/8+\varepsilon} n)$ update time for an arbitrarily small
constant $\varepsilon>0$.

In the case of 3-sided queries, our update time reduces to
$O(\log^{1/2+\varepsilon} n)$, improving Wilkinsonâ€™s previous bound
[ESA 2014] of $O(\log^{2/3+\varepsilon} n)$.