Let μ be a function that assigns a real number μ(P) ≥ 0 to any point set P in Rd; 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 Rd. 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.

Additional Metadata
Conference 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010
Citation
Nekrich, Y. (Yakov), & Smid, M. (2010). Approximating range-Aggregate queries using coresets. Presented at the 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010.