Dynamic colored orthogonal range searching

Timothy M. Chan, Zhengcheng Huang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication29th Annual European Symposium on Algorithms, ESA 2021
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772044
DOIs
StatePublished - Sep 1 2021
Event29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal
Duration: Sep 6 2021Sep 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume204
ISSN (Print)1868-8969

Conference

Conference29th Annual European Symposium on Algorithms, ESA 2021
Country/TerritoryPortugal
CityVitual, Lisbon
Period9/6/219/8/21

Keywords

  • Dynamic data structures
  • Range searching
  • Word RAM

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Dynamic colored orthogonal range searching'. Together they form a unique fingerprint.

Cite this