Space-time tradeoff for approximate spherical range counting

We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in Rd along with a positive approximation factor ε, the goal is to preprocess the points so that, given any Euclidean ball B, we can return the number of points of any subset of S that contains all the points within a (1 − ε)-factor contraction of B, but contains no points that lie outside a (1 + ε)-factor expansion of B. In many applications of range searching it is desirable to offer a tradeoff between space and query time. We present here the first such tradeoffs for approximate range counting queries. Given 0 < ε ≤ 1/2 and a parameter γ, where 2 ≤ γ ≤ 1/ε, we show how to construct a data structure of space O(nγd log(1/ε)) that allows us to answer ε-approximate spherical range counting queries in time O(log(nγ) + 1/(εγ)d−1). The data structure can be built in time O(nγd log(n/ε) log(1/ε)). Here n, ε, and γ are asymptotic quantities, and the dimension d is assumed to be a fixed constant. At one extreme (low space), this yields a data structure of space O(n log(1/ε)) that can answer approximate range queries in time O(log n+(1/ε)d−1) which, up to a factor of O(log 1/ε