Better data structures for colored orthogonal range reporting

Timothy M. Chan, Yakov Nekrich

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

Abstract

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).

Original languageEnglish (US)
Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
EditorsShuchi Chawla
PublisherAssociation for Computing Machinery
Pages627-636
Number of pages10
ISBN (Electronic)9781611975994
StatePublished - 2020
Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
Duration: Jan 5 2020Jan 8 2020

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2020-January

Conference

Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
Country/TerritoryUnited States
CitySalt Lake City
Period1/5/201/8/20

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Better data structures for colored orthogonal range reporting'. Together they form a unique fingerprint.

Cite this