Abstract

Given a set of \(n\) colored points \(P \subset \R^d\) we wish to store \(P\) such that, given some query region \(Q\), we can efficiently report the colors of the points appearing in the query region, along with their frequencies. This is the color frequency reporting problem. We study the case where query regions \(Q\) are axis-aligned boxes or dominance ranges. If \(Q\) contains \(k\) colors, the main goal is to achieve “strictly output sensitive” query time \(O(f(n) + k)\). Firstly, we show that, for every \(s \in \{ 2, \dots, n \}\), there exists a simple \(O(ns\log_s n)\) size data structure for points in \(\R^2\) that allows frequency reporting queries in \(O(\log n + k\log_s n)\) time. Secondly, we give a lower bound for the weighted version of the problem in the arithmetic model of computation, proving that with \(O(m)\) space one can not achieve query times better than \(\Omega\left(\phi \frac{\log (n / \phi)}{\log (m / n)}\right)\), where \(\phi\) is the number of possible colors. This means that our data structure is near-optimal. We extend these results to higher dimensions as well. Thirdly, we present a transformation that allows us to reduce the space usage of the aforementioned datastructure to \(O(n(s \phi)^\eps \log_s n)\). Finally, we give an \(O(n^{1+\eps} + m \log n + K)\)-time algorithm that can answer \(m\) dominance queries \(\R^2\) with total output complexity \(K\), while using only linear working space.

Corresponding Publications

On Strictly Output-Sensitive Color Frequency Reporting

Erwin Glazenburg, Frank Staals

SOFSEM 2026: Theory and Practice of Computer Science, 2026

Invited for a special in DMTCS on SOFSEM 2026

Download Local Copy View Slides Export Citation

@incollection{type2counting2026,
  author = {Glazenburg, Erwin and Staals, Frank},
  title = {On Strictly Output-Sensitive Color Frequency Reporting},
  booktitle = {{SOFSEM} 2026: Theory and Practice of Computer Science},
  series = {LNCS},
  year = {2026},
  location = {Krak{\'{o}}w, Poland},
  publisher = {Springer},
  category = {datastructures},
  pages = {246--259},
  doi = {10.1007/978-3-032-17801-5_18},
  url = {https://doi.org/10.1007/978-3-032-17801-5_18},
  note = {Invited for a special in DMTCS on SOFSEM 2026},
}