Dynamic Orthogonal Range Searching on the RAM, Revisited



Tsakalidis, K ORCID: 0000-0001-6470-9332 and Chan, Timothy M
(2018) Dynamic Orthogonal Range Searching on the RAM, Revisited. Journal of Computational Geometry, 9 (2). 45 - 66.

This is the latest version of this item.

[img] Text
jocgrevision.pdf - Accepted Version
Available under License : See the attached licence file.

Download (463kB)
[img] Text
440-1726-1-SM.pdf - Accepted Version
Available under License : See the attached licence file.

Download (450kB)
[img] Text
440-1726-1-SM.pdf - OA Published Version
Available under License : See the attached licence file.

Download (494kB)
[img] Text
440-1863-1-PB.pdf - OA Published Version
Available under License : See the attached licence file.

Download (494kB)

Abstract

We study a longstanding problem in computational geometry: 2-d dynamic orthogonal range reporting. We present a new data structure achieving O(lognloglogn+k)O(log⁡nlog⁡log⁡n+k) optimal query time (amortized) and O(log2/3+o(1)n)O(log2/3+o(1)⁡n) update time (amortized) in the word RAM model, where nn is the number of data points and kk 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(log7/8+εn)O(log7/8+ε⁡n) update time for an arbitrarily small constant ε>0ε>0. In the case of 3-sided queries, our update time reduces to O(log1/2+εn)O(log1/2+ε⁡n), improving Wilkinson's previous bound [ESA 2014] of O(log2/3+εn)O(log2/3+ε⁡n). We also obtain an improved result in higher dimensions d≥3d≥3.

Item Type: Article
Depositing User: Symplectic Admin
Date Deposited: 09 Oct 2020 08:47
Last Modified: 10 Sep 2021 03:10
DOI: 10.20382/jocg.v9i2a5
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3103842

Available Versions of this Item