The Space Complexity of 2-Dimensional Approximate Range Counting
Zhewei Wei, Ke Yi · 2013
We study the problemof2-dimensionalorthogonalrangecountingwith additiveerror. Given a set P of n points drawn from an n×n grid and an error parameter ε, 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 ∩ R with additive error εn. A well-known solution for this problem is the ε-approximation. Informally speaking, an ε-approximation of P is a subset A ⊆ P that allows us to estimate the number of points in P ∩ R by counting the number of points in A ∩ R. It is known that an ε-approximation of size O ( 1 1 ε log2.5