Optimal lower bounds for epsilon-nets for lines in the plane

Abstract

We prove that, for arbitrarily small positive $\epsilon$, there is a finite planar point set $P$ such that every $\epsilon$-net for the range space induced on $P$ by straight lines has cardinality $\Omega (1/\epsilon \cdot \log (1/\epsilon ))$. This matches the classical upper bound for range spaces with bounded VC-dimension due to Haussler and Welzl and confirms a prediction of Alon.

arXiv comment6 pages