On strictly output sensitive color frequency reporting

Given a set of n colored points P ⊂ Rᵈ 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 ∈ \ 2, , n \, there exists a simple O(nslogₛ n) size data structure for points in R² that allows frequency reporting queries in O(log n + klogₛ 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 Ω(ϕlog (n / ϕ)/log (m / n)), where $ϕ$ 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 data structure to O(n(s ϕ)^ε logₛ n). Finally, we give an O(n1+ε + m log n + K)-time algorithm that can answer m dominance queries in R² with total output complexity K, while using only linear working space. new version for submission to DMTCS journal