Epsilon-Nets for Halfspaces Revisited

Abstract

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 )$. We give five proofs of this result, which are arguably simpler than previous proofs \cite{msw-hnlls-90, cv-iaags-07, pr-nepen-08}. We also consider several related variants of this result, including the case of points and pseudo-disks in the plane.