Dynamic Orthogonal Range Searching on the RAM, Revisited.

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.

There is a more recent version of this item available.

	Text jocgrevision.pdf - Author Accepted Manuscript Download (463kB)
	Text 440-1726-1-SM.pdf - Published version 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(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:	18 Mar 2019 11:55
Last Modified:	19 Jan 2023 00:57
DOI:	10.4230/LIPIcs.SoCG.2017.28
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3033791