Fully Dynamic Orthogonal Range Reporting on RAM
Christian Worm Mortensen · SIAM Journal on Computing · 2006
We show that there exists a constant $\omega < 1$ such that the fully dynamic d-dimensional orthogonal range reporting problem for any constant $d \ge 2$ can be solved in time $O(\log^{\omega+d-2} n)$ for updates and time $O((\log n / \log\log n)^{d-1} + r)$ for queries. Here n is the number of points stored and r is the number of points reported. The space usage is $O(n \log^{\omega+d-2} n)$. For $d=2$ our results are optimal in terms of time per operation, and this is the main contribution of this paper. Also for $d=2$, we give a new improved fully dynamic structure supporting 3-sided queries. The model of computation is a unit cost RAM@. We order the coordinates of points using list order as defined in the paper.