Stronger bounds for weak epsilon-nets in higher dimensions

Given a finite point set P in R d , and ϵ > 0 we say that N ⊆ R d is a weak ϵ-net if it pierces every convex set K with |K ∩ P | ≥ ϵ|P |. We show that for any finite point set in dimension d ≥ 3, and any ϵ > 0, one can construct a weak ϵ-net whose cardinality is To be precise, our weak ϵ-net has cardinality O 1 ϵ α d +γ for any γ > 0, with This is the first significant improvement of the bound of Õ 1 ϵ d that was obtained in 1993 by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl for general point sets in dimension d ≥ 3.