Approximate Maximum Halfspace Discrepancy

Michael Matheny, Jeff M. Phillips

Consider the geometric range space $(X,{\mathcal{H}}_d)$ where $X\subset {\mathbb{R}}^d$ and ${\mathcal{H}}_d$ is the set of ranges defined by $d$-dimensional halfspaces. In this setti…