{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiclqsihfk6v6ekrfxbjtfnzymdfst46kbpan2iu5cevdzkpxktjau",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mgw2pj4ygpc2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.11898v1",
  "publishedAt": "2026-03-13T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Erwin Glazenburg",
    "Frank Staals"
  ],
  "textContent": "**Authors:** Erwin Glazenburg, Frank Staals\n\nGiven 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 $Ω\\left(φ\\frac{\\log (n / φ)}{\\log (m / n)}\\right)$, 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 datastructure to $O(n(s φ)^\\varepsilon \\log_s n)$. Finally, we give an $O(n^{1+\\varepsilon} + m \\log n + K)$-time algorithm that can answer $m$ dominance queries $\\mathbb{R}^2$ with total output complexity $K$, while using only linear working space.",
  "title": "On strictly output sensitive color frequency reporting"
}