Range mode queries, set intersection queries, and colored range queries

Michiel Smid

Carleton University

In this talk, we consider three data structure problems:

- Given an array $A$, answer queries of the following type: For two query values $i$ and $j$, report the mode in the subarray $A[i \ldots j]$.
- Given a sequence $S_1,S_2,\ldots,S_m$ of sets, answer queries of the following type: For two query values $i$ and $j$, decide whether or not $S_i$ and $S_j$ are disjoint.
- Given a set $S$ of $n$ points in the plane, where each point has some color, answer queries of the following type: For a given query rectangle $R$ and a given integer $k$, decide whether or not there is a color that occurs at least $k$ times in the set $S \cap R$.

I will show that Problem 1 and Problem 3 are equivalent, up to a polylogarithmic factor. I will also show that Problem 2 and Problem 3, with $k=2$, are equivalent, up to a polylogarithmic factor.