Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
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|) + logN + 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) + logN + K) time, improving the best previously known query times of O(|Q|log(N/|Q|) + K) and O(2LL + logN + K). Finally, we give an optimal data structure for three-sided ranges for the case L = O(log N). Copyright © 2014 by the Society for Industrial and Applied Mathematics.
Original language | English |
---|---|
Title of host publication | Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms : SODA 2014; Portland, OR; United States; 5 January 2014 through 7 January 2014 |
Editors | Chandra Chekuri |
Number of pages | 10 |
Publisher | Association for Computing Machinery |
Publication year | 1 Jan 2014 |
Pages | 1414-1423 |
ISBN (print) | 9781611973389 |
Publication status | Published - 1 Jan 2014 |
Event | Annual ACM-SIAM Symposium on Discrete Algorithms - Portland, OR, United States Duration: 5 Jan 2014 → 7 Jan 2014 Conference number: 25 |
Conference | Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Nummer | 25 |
Land | United States |
By | Portland, OR |
Periode | 05/01/2014 → 07/01/2014 |
See relations at Aarhus University Citationformats
ID: 81852026