TY - GEN
T1 - Better data structures for colored orthogonal range reporting
AU - Chan, Timothy M.
AU - Nekrich, Yakov
N1 - Publisher Copyright:
Copyright © 2020 by SIAM
PY - 2020
Y1 - 2020
N2 - Range searching on categorical, or “colored”, data has been studied extensively for over two decades. In this paper, we obtain the current best results for perhaps the most basic, and most often studied, version of the geometric problem: colored orthogonal range reporting. Given n colored points in two-dimensional space [U]2, we present a data structure with O(n log3/4+ε n) space, for an arbitrarily small constant ε > 0, so that all k distinct colors in any axis-aligned query rectangle can be reported in (optimal) O(log log U + k) time; this is the first method to break the O(nlog n) space barrier. In three dimensions, we present a data structure with O(n log9/5+ε n) space and O(log n/log log n + k) time; this improves the previous space bound of O(n log4 n).
AB - Range searching on categorical, or “colored”, data has been studied extensively for over two decades. In this paper, we obtain the current best results for perhaps the most basic, and most often studied, version of the geometric problem: colored orthogonal range reporting. Given n colored points in two-dimensional space [U]2, we present a data structure with O(n log3/4+ε n) space, for an arbitrarily small constant ε > 0, so that all k distinct colors in any axis-aligned query rectangle can be reported in (optimal) O(log log U + k) time; this is the first method to break the O(nlog n) space barrier. In three dimensions, we present a data structure with O(n log9/5+ε n) space and O(log n/log log n + k) time; this improves the previous space bound of O(n log4 n).
UR - http://www.scopus.com/inward/record.url?scp=85084092322&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85084092322&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85084092322
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 627
EP - 636
BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
A2 - Chawla, Shuchi
PB - Association for Computing Machinery
T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Y2 - 5 January 2020 through 8 January 2020
ER -