2026-07-22T23:50:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14609 2024-03-06T10:54:26Z ddc:004 open_access

Dynamic Colored Orthogonal Range Searching Chan, Timothy M. Huang, Zhengcheng Range searching dynamic data structures word RAM 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(log^{1+o(1)} n + klog^{1/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(log^{2+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(log^{1+o(1)} n + klog^{3/4+o(1)}n) query time and O(log^{3/2+o(1)}n) update time (amortized). We also mention extensions to higher constant dimensions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Timothy M. Chan and Zhengcheng Huang 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.28 urn:nbn:de:0030-drops-146090 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.28 eng https://creativecommons.org/licenses/by/4.0/legalcode