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).
pp. 45-66.
This is the latest version of this item.
Text
jocgrevision.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (463kB) |
|
Text
440-1726-1-SM.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (450kB) |
|
Text
440-1726-1-SM.pdf - Published version Available under License : See the attached licence file. Download (494kB) |
|
Text
440-1863-1-PB.pdf - 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(lognloglogn+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: | 18 Jan 2023 23:29 |
DOI: | 10.20382/jocg.v9i2a5 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3103842 |
Available Versions of this Item
-
Dynamic orthogonal range searching on the RAM, Revisited. (deposited 16 Jan 2019 11:17)
-
Dynamic Orthogonal Range Searching on the RAM, Revisited. (deposited 18 Mar 2019 11:55)
- Dynamic Orthogonal Range Searching on the RAM, Revisited. (deposited 09 Oct 2020 08:47) [Currently Displayed]
-
Dynamic Orthogonal Range Searching on the RAM, Revisited. (deposited 18 Mar 2019 11:55)