Dynamic Orthogonal Range Searching on the RAM, Revisited
| Autor: | Tsakalidis, K, Chan, Timothy M |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: | |
| Zdroj: | J. Comput. Geom. JoCG LIPIcs : Leibniz International Proceedings in Informatics Leibniz International Proceedings in Informatics, LIPIcs Journal of Computational Geometry |
| Popis: | We study a longstanding problem in computational geometry: 2-d dynamic orthogonal range reporting. We present a new data structure achieving $O\left(\frac{\log n}{\log\log n} + k\right)$ optimal query time (amortized) and $O\left(\log^{2/3+o(1)}n\right)$ 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\left(\log^{7/8+\varepsilon}n\right)$ update time for an arbitrarily small constant $\varepsilon>0$. In the case of 3-sided queries, our update time reduces to $O\left(\log^{1/2+\varepsilon}n\right)$, improving Wilkinson's previous bound [ESA 2014] of $O\left(\log^{2/3+\varepsilon}n\right)$. We also obtain an improved result in higher dimensions $d\geq 3$. Journal of Computational Geometry, Vol. 9 No. 2 (2018): Special Issue of Selected Papers from SoCG 2017 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|