#
The Space Complexity of 2-Dimensional Approximate Range Counting

##
William Eric Devanny

(a SODA 2013 paper by by Zhewei Wei and Ke Yi)

We study the problem of 2-dimensional orthogonal range counting with
additive error. Given a set $P$ of $n$ points drawn from an $n\times n$ grid
and an error parameter $\eps$, the goal is to build a data structure, such
that for any orthogonal range $R$, the data structure can return the number
of points in $P\cap R$ with additive error $\eps n$. A well-known solution
for this problem is the {\em $\eps$-approximation}. Informally speaking, an
$\eps$-approximation of $P$ is a subset $A\subseteq P$ that allows us to
estimate the number of points in $P\cap R$ by counting the number of points
in $A\cap R$. It is known that an $\eps$-approximation of size
$O(\frac{1}{\eps} \log^{2.5} \frac{1}{\eps})$ exists for any $P$ with
respect to orthogonal ranges, and the best lower bound is
$\Omega(\frac{1}{\eps} \log \frac{1}{\eps})$.
The $\eps$-approximation is a rather restricted data structure, as we are
not allowed to store any information other than the coordinates of a subset
of points in $P$. In this paper, we explore what can be achieved without any
restriction on the data structure. We first describe a data structure that
uses $O(\frac{1}{\eps} \log \frac{1} {\eps} \log\log \frac{1}{\eps} \log n)$
bits that answers queries with error $\eps n$. We then prove a lower bound
that any data structure that answers queries with error $O(\log n)$ must use
$\Omega(n\log n)$ bits. This lower bound has two consequences: 1) answering
queries with error $O(\log n)$ is as hard as answering the queries exactly;
and 2) our upper bound cannot be improved in general by more than an $O(\log
\log \frac{1}{\eps})$ factor.