An Improved Bound for Weak Epsilon-Nets in the Plane

Abstract

We show that for any finite set $P$ of points in the plane and $\epsilon >0$ there exist $O\left(\frac{1}{{\epsilon }^{3/2+\gamma }}\right)$ points in ${\mathbb{R}}^2$, for arbitrary small $\gamma >0$, that pierce every convex set $K$ with $|K\cap P|\ge \epsilon |P|$. This is the first improvement of the bound of $O\left(\frac{1}{{\epsilon }^2}\right)$ that was obtained in 1992 by Alon, Bárány, Füredi and Kleitman for general point sets in the plane.

A preliminary version to appear in the proceedings of FOCS 2018. Full version to appear in Journal of ACM