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

Ilay Hoshen, Wojciech Samotij

Abstract

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

Disclosure

“raph con- −1 tainer lemma from [7] and gave a lower bound of order 1/ε · log(1/ε) · log log(1/ε) . During the preparation of this manuscript, we asked OpenAI’s ChatGPT for comments on a prelimi- nary draft. It suggested replacing the container argument with an averaging argument whose streamlined version is the current proof of Theorem 3.2. Acknowledgement. The second author would like to thank Noga Al”
PDF page 2

Classification: Proof ideas or individual proof-step assistance
Multiplier: 8
Verified: 2026-08-23T05:10:37.350918Z

Structural counts

Pages 6 pdf

Theorems 2 source

Lemmas 5 source

Propositions 0 source

Corollaries 0 source

Definitions 0 source

Displayed equations 26 source

Bibliography entries 16 source

Appendix pages 0 estimated

Count notes

Source counts use the expanded primary TeX file eps-nets-lower-bound.tex.
Appendix pages include the first PDF page with an explicit Appendix heading through the final page.