A Non-linear Lower Bound for Planar Epsilon-Nets
Noga Alon · 2010
We show that the minimum possible size of an ϵ-net for point objects and line (or rectangle)-ranges in the plane is (slightly) bigger than linear in 1/ϵ. This settles a problem raised by Matousek, Seidel and Welzl in 1990.