Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges

Abstract

A family $\mathcal{R}$ of ranges and a set $X$ of points together define a range space $(X,\mathcal{R}{|}_X)$, where $\mathcal{R}{|}_X=\{X\cap h\mid h\in \mathcal{R}\}$. We want to find a structure to estimate the quantity $|X\cap h|/|X|$ for any range $h\in \mathcal{R}$ with the $(\rho ,\epsilon )$-guarantee: (i) if $|X\cap h|/|X|>\rho$, the estimate must have a relative error $\epsilon$; (ii) otherwise, the estimate must have an absolute error $\rho \epsilon$. The objective is to minimize the size of the structure. Currently, the dominant solution is to compute a relative $(\rho ,\epsilon )$-approximation, which is a subset of $X$ with $\tilde{O}(\lambda /(\rho {\epsilon }^2))$ points, where $\lambda$ is the VC-dimension of $(X,\mathcal{R}{|}_X)$, and $\tilde{O}$ hides polylog factors. This paper shows a more general bound sensitive to the content of $X$. We give a structure that stores $O(\log (1/\rho ))$ integers plus $\tilde{O}(\theta \cdot (\lambda /{\epsilon }^2))$ points of $X$, where $\theta$ - called the disagreement coefficient - measures how much the ranges differ from each other in their intersections with $X$. The value of $\theta$ is between 1 and $1/\rho$, such that our space bound is never worse than that of relative $(\rho ,\epsilon )$-approximations, but we improve the latter's $1/\rho$ term whenever $\theta =o(\frac{1}{\rho \log (1/\rho )})$. We also prove that, in the worst case, summaries with the $(\rho ,1/2)$-guarantee must consume $\Omega (\theta )$ words even for $d=2$ and $\lambda \le 3$. We then constrain $\mathcal{R}$ to be the set of halfspaces in ${\mathbb{R}}^d$ for a constant $d$, and prove the existence of structures with $o(1/(\rho {\epsilon }^2))$ size offering $(\rho ,\epsilon )$-guarantees, when $X$ is generated from various stochastic distributions. This is the first formal justification on why the term $1/\rho$ is not compulsory for "realistic" inputs.

SoCG'19