Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions

Abstract Given a finite point set P in $$\mathbb {R}^d$$ R d , and $$\epsilon >0$$ ϵ > 0 we say that $$N\subseteq \mathbb {R}^d$$ N ⊆ R d is a weak $$\epsilon $$ ϵ -net if it pierces every convex set K with $$|K\cap P|\ge \epsilon |P|$$ | K ∩ P | ≥ ϵ | P | . We show that for any finite point set in dimension $$d\ge 3$$ d ≥ 3 , and any $$\epsilon >0$$ ϵ > 0 , one can construct a weak $$\epsilon $$ ϵ -net whose cardinality is $$\displaystyle O^*\left( \frac{1}{\epsilon ^{2.558}}\right) $$ O ∗ 1 ϵ 2.558 in dimension $$d=3$$ d = 3 , and $$\displaystyle o\left( \frac{1}{\epsilon ^{d-1/2}}\right) $$ o 1 ϵ d - 1 / 2 in all dimensions $$d\ge 4$$ d ≥ 4 . (In the sequel, the $$O^*(x)$$ O ∗ ( x