Natan Rubin

Given a finite point set P in Rd, and ϵ>0 we say that N⊆Rd 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 O∗1ϵ2.558 in dimension d=3, and o1ϵd-1/2 in all dimensions d≥4. (In the sequel, the O∗(x) notation hides multiplicative factors that are bounded by xγ, for arbitrary small γ>0, whereas the O~(x)-notation hides multiplicative factors that are polylogarithmic in x.) To be precise, our weak ϵ-net has cardinality O1ϵαd+γ for any γ>0, with (Formula presented.) This is the first significant improvement of the bound of O~1ϵd that was obtained in 1993 by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl for general point sets in dimension d≥3.