Epsilon-Nets for Halfspaces Revisited

Sariel Har-Peled, Haim Kaplan, Micha Sharir +1

Given a set $P$ of $n$ points in ${\mathbb{R}}^3$, we show that, for any $\epsilon >0$, there exists an $\epsilon$-net of $P$ for halfspace ranges, of size $O(1/\epsilon )$.…