Abstract

A range counting problem is specified by a set $P$ of size $|P|=n$ of points in $\mathbb{R}^{d}$ , an integer weight $x_{p}$ associated to each point $p\in P$ , and a range space $\mathcal{R}\subseteq 2^{P}$ . Given a query range $R\in\mathcal{R}$ , the output is $R(\mathbf{x})=\sum_{p\in R}{x_{p}}$ . The average squared error of an algorithm $\mathcal{A}$ is $\frac{1}{|\mathcal{R}|}\sum_{R\in\mathcal{R}}{\left(\mathcal{A}(R,\mathbf{x})-R(\mathbf{x})\right)^{2}}$ . Range counting for different range spaces is a central problem in Computational Geometry.