Chan, TM and Tsakalidis, K 
ORCID: 0000-0001-6470-9332
(2017)
Dynamic orthogonal range searching on the RAM, Revisited.
.
 | There is a more recent version of this item available. |
![[img]](https://livrepository.liverpool.ac.uk/style/images/fileicons/text.png) |
Text
jocgrevision.pdf - Author Accepted Manuscript Download (463kB) |
Abstract
© Timothy M. Chan and Konstantinos Tsakalidis. 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(log2/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 (log7/8/ϵn) update time for an arbitrarily small constant ϵ. In the case of 3-sided queries, our update time reduces to O (log1/2+ϵn), improving Wilkinson's previous bound [ESA 2014] of O(log2/3+ϵ).
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Depositing User: | Symplectic Admin |
| Date Deposited: | 16 Jan 2019 11:17 |
| Last Modified: | 19 Jan 2023 01:06 |
| DOI: | 10.4230/LIPIcs.SoCG.2017.28 |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3031341 |
Available Versions of this Item
- Dynamic orthogonal range searching on the RAM, Revisited. (deposited 16 Jan 2019 11:17) [Currently Displayed]
Dimensions
Dimensions
