Aarhus University Seal

Fast Computation of Output-Sensitive Maxima in a Word RAM

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-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 languageEnglish
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms : SODA 2014; Portland, OR; United States; 5 January 2014 through 7 January 2014
EditorsChandra Chekuri
Number of pages10
PublisherAssociation for Computing Machinery
Publication year1 Jan 2014
ISBN (print)9781611973389
Publication statusPublished - 1 Jan 2014
EventAnnual ACM-SIAM Symposium on Discrete Algorithms - Portland, OR, United States
Duration: 5 Jan 20147 Jan 2014
Conference number: 25


ConferenceAnnual ACM-SIAM Symposium on Discrete Algorithms
LandUnited States
ByPortland, OR

See relations at Aarhus University Citationformats

ID: 81852026