An Improved Bound for Weak Epsilon-Nets in the Plane
Natan Rubin · 2018
We show that for any finite point set P in the plane and ε>0 there exist O(1/ε3/2+γ) points, for arbitrary small γ>0, that pierce every convex set K with |K∩ P|≥ ε |P|. This is the first improvement of the bound of O(1)ε2) that was obtained in 1992 by Alon, Bárány, Füredi and Kleitman for general point sets in the plane.