Natan Rubin: Stronger bounds for weak Epsilon-Nets

Given a finite point set $P$ in $R^d$, and $ϵ>0$ we say that a point set $N$ in $R^d$ is a weak $ϵ$-net if it pierces every convex set $K$ with $|K\cap P|\ge ϵ|P|$. Let $d\ge 3$. We show that for any finite point set in $R^d$, and any $ϵ>0$, there exists a weak $ϵ$-net of cardinality $O\left(1/{ϵ}^{d-1/2+\delta }\right)$, where $\delta >0$ is an arbitrary small constant. This is the first improvement of the bound of $O^{\ast }\left(1/{ϵ}^d\right)$ that was obtained in 1994 by Chazelle, Edelsbrunner, Grini, Guibas, Sharir, and Welzl for general point sets in dimension $d\ge 3$.