PhD Seminar • Algorithms and Complexity: Succinct Color Searching in One Dimension
Hicham El-Zein, PhD candidate
David R. Cheriton School of Computer Science
We present succinct data structures for one-dimensional color reporting and color counting problems. We are given a set of $n$ points with integer coordinates in the range $[1,m]$ and every point is assigned a color from the set $\{\,1,\ldots,\sigma\,\}$. A color reporting query asks for the list of distinct colors that occur in a query interval $[a,b]$ and a color counting query asks for the number of distinct colors in $[a,b]$.