Paper Info
Title
Concurrent range reporting in two-dimensional space
Abstract
In the concurrent range reporting (CRR) problem, the input is L disjoint sets S1, ..., SL of points in Rd with a total of N points. The goal is to preprocess the sets into a structure such that, given a query range r and an arbitrary set Q ⊆ {1, ..., L}, we can efficiently report all the points in Si ∩ r for each i ε Q. The problem was studied as early as 1986 by Chazelle and Guibas [9] and has recently re-emerged when studying higher-dimensional complexity of orthogonal range reporting [2, 3]. We focus on the one- and two-dimensional cases of the problem. We prove that in the pointer-machine model (as well as comparison models such as the real RAM model), answering queries requires Ω(|Q| log(L/|Q|) + log N + K) time in the worst case, where K is the number of output points. In one dimension, we achieve this query time with a linear-space dynamic data structure that requires optimal O(log N) time to update. We also achieve this query time in the static case for dominance and halfspace queries in the plane. For three-sided ranges, we get close to within an inverse Ackermann (α(·)) factor: we answer queries in O(|Q| log(L/|Q|)α(L) + log N + K) time, improving the best previously known query times of O(|Q|log(N/|Q|) + K) and O(2LL + log N + K). Finally, we give an optimal data structure for three-sided ranges for the case L = O(log N).
Year
DOI
Venue
2014
10.5555/2634074.2634147
SODA
Keywords
Field
DocType
algorithms,design,models of computation,complexity measures and classes,general,theory
Real RAM,Discrete mathematics,Binary logarithm,Data structure,Inverse,Ackermann function,Combinatorics,Disjoint sets,Two-dimensional space,Dynamic data structures,Mathematics
Conference
ISBN
Citations 
PageRank 
978-1-61197-338-9
0
0.34
References 
Authors
12
4
Name
Order
Citations
PageRank
Peyman Afshani125623.84
Cheng Sheng233414.57
Yufei Tao37231316.71
Bryan T. Wilkinson4434.18