Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions

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