On strictly output sensitive color frequency reporting

Abstract

Given a set of $n$ colored points $P\subset {\mathbb{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 \emph{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 ${\mathbb{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 $\hat{I}\text{c◯}\left(\ddot{I}•\frac{\log (n/\ddot{I}•)}{\log (m/n)}\right)$, where $\ddot{I}•$ 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\ddot{I}•{)}^{\epsilon }{\log }_{s}n)$. Finally, we give an $O(n^{1+\epsilon }+m\log n+K)$-time algorithm that can answer $m$ dominance queries in ${\mathbb{R}}^2$ with total output complexity $K$, while using only linear working space.

new version for submission to DMTCS journal