Approximating Range-Aggregate Queries using Coresets
Yakov Nekrich, Michiel Smid · 2010
Let µ be a function that assigns a real number µ(P) ≥ 0 to any point set P in R d; for example, µ(P) can be the diameter or radius of the smallest enclosing ball of P. Let S be a set of n points in R d. We consider the problem of storing S in a data structure, such that for any query rectangle Q, we can efficiently compute an approximation to the value µ(S ∩ Q). Our solutions are obtained by combining range-searching techniques with coresets. 1