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). 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)

Official URL: https://journals.carleton.ca/jocg/index.php/jocg/a...

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:	18 Jan 2023 23:29
DOI:	10.20382/jocg.v9i2a5
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3103842