BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

An improved bound on weak epsilon nets in the plane Rubin, Natan


We show that for any set $P$ of $n$ points in the plane and $\eps>0$ there exists a set of $o\left(\frac{1}{\eps^{1.7}}\right)$ points in the plane that pierce every convex set $K$ with $|K\cap P|\geq \eps |P|$. This is the first improvement of the 1992 upper bound $O\left(\frac{1}{\eps^2}\right)$ of Alon, Bárány, Füredi, and Kleitman.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International