Distribution-Sensitive Bounds on Relative Approximations of Geometric Ranges

Yufei Tao, Yu Wang

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…