On Strictly Output-Sensitive Color Frequency Reporting

Given a set of n colored points P⊂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). We show that, for every s∈{2,⋯,n}, there exists a simple O(nslog_sn)-size data structure for points in R² that allows frequency reporting queries in O(logn+klog_sn) time. Furthermore, we give a lower bound for the weighted version of the problem in the arithmetic model, proving that with O(m) space one can not achieve query times better than Ωϕlog(n/ϕ)log(2m/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. Finally, we give an O(n^1+ε+mlogn+K)-time algorithm that can answer m dominance queries R² with total output complexity K, while using only linear working space.