Chan, Timothy M and Tsakalidis, Konstantinos 
ORCID: 0000-0001-6470-9332
(2017)
Dynamic Orthogonal Range Searching on the RAM, Revisited.
In: 33rd International Symposium on Computational Geometry.
|
Text
LIPIcs-SoCG-2017-28.pdf - Published version Download (498kB) | Preview |
Abstract
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(log^{2/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(log^{7/8+epsilon}n) update time for an arbitrarily small constant epsilon. In the case of 3-sided queries, our update time reduces to O(log^{1/2+epsilon}n), improving Wilkinson's previous bound [ESA 2014] of O(log^{2/3+epsilon}n).
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | dynamic data structures, range searching, computational geometry |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 12 Oct 2020 13:53 |
| Last Modified: | 18 Jan 2023 23:28 |
| DOI: | 10.4230/LIPIcs.SoCG.2017.28 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3104058 |
Dimensions
Dimensions
