{"id":"arxiv/2608.11457","url":"https://arxiv.org/abs/2608.11457","tags":["math.CO"],"score":0,"title":"Optimal lower bounds for epsilon-nets for lines in the plane","domain":"math.CO","source":"arxiv","authors":["Ilay Hoshen","Wojciech Samotij"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}