TY - GEN
T1 - Dynamic colored orthogonal range searching
AU - Chan, Timothy M.
AU - Huang, Zhengcheng
N1 - Funding Information:
Supported by NSF Grant CCF-1814026.
Funding Information:
Supported by NSF Grant CCF-1814026. ? Timothy M. Chan and Zhengcheng Huang; licensed under Creative Commons License CC-BY 4.0 29th Annual European Symposium on Algorithms (ESA 2021).
Publisher Copyright:
© Timothy M. Chan and Zhengcheng Huang; licensed under Creative Commons License CC-BY 4.0
PY - 2021/9/1
Y1 - 2021/9/1
N2 - In the colored orthogonal range reporting problem, we want a data structure for storing n colored points so that given a query axis-aligned rectangle, we can report the distinct colors among the points inside the rectangle. This natural problem has been studied in a series of papers, but most prior work focused on the static case. In this paper, we give a dynamic data structure in the 2D case which can answer queries in O(log1+o(1) n + k log1/2+o(1) n) time, where k denotes the output size (the number of distinct colors in the query range), and which can support insertions and deletions in O(log2+o(1) n) time (amortized) in the standard RAM model. This is the first fully dynamic structure with polylogarithmic update time whose query cost per color reported is sublogarithmic (near √log n). We also give an alternative data structure with O(log1+o(1) n + k log3/4+o(1) n) query time and O(log3/2+o(1) n) update time (amortized). We also mention extensions to higher constant dimensions.
AB - In the colored orthogonal range reporting problem, we want a data structure for storing n colored points so that given a query axis-aligned rectangle, we can report the distinct colors among the points inside the rectangle. This natural problem has been studied in a series of papers, but most prior work focused on the static case. In this paper, we give a dynamic data structure in the 2D case which can answer queries in O(log1+o(1) n + k log1/2+o(1) n) time, where k denotes the output size (the number of distinct colors in the query range), and which can support insertions and deletions in O(log2+o(1) n) time (amortized) in the standard RAM model. This is the first fully dynamic structure with polylogarithmic update time whose query cost per color reported is sublogarithmic (near √log n). We also give an alternative data structure with O(log1+o(1) n + k log3/4+o(1) n) query time and O(log3/2+o(1) n) update time (amortized). We also mention extensions to higher constant dimensions.
KW - Dynamic data structures
KW - Range searching
KW - Word RAM
UR - http://www.scopus.com/inward/record.url?scp=85115104207&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115104207&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2021.28
DO - 10.4230/LIPIcs.ESA.2021.28
M3 - Conference contribution
AN - SCOPUS:85115104207
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 29th Annual European Symposium on Algorithms, ESA 2021
A2 - Mutzel, Petra
A2 - Pagh, Rasmus
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 29th Annual European Symposium on Algorithms, ESA 2021
Y2 - 6 September 2021 through 8 September 2021
ER -