Discrete & Computational Geometry Математика

Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions

Natan Rubin
Springer Nature · 2026-11-06 · DOI 10.1007/s00454-026-00878-y

Аннотация

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 ) notation hides multiplicative factors that are bounded by $$x^{\gamma }$$ x γ , for arbitrary small $$\gamma >0$$ γ > 0 , whereas the $$\tilde{O}(x)$$ O ~ ( x ) -notation hides multiplicative factors that are polylogarithmic in x .) To be precise, our weak $$\epsilon $$ ϵ -net has cardinality $$\displaystyle O\left( \frac{1}{\epsilon ^{\alpha _d+\gamma }}\right) $$ O 1 ϵ α d + γ for any $$\gamma >0$$ γ > 0 , with $$ \alpha _d= {\left\{ \begin{array}{ll} 2.558 & {\text {if}} \ d=3\\ 3.48 & {\text {if}} \ d=4\\ \left( d+\sqrt{d^2-2d}\right) /2 & {\text {if}} \ d\ge 5. \end{array}\right. } $$ α d = 2.558 if d = 3 3.48 if d = 4 d + d 2 - 2 d / 2 if d ≥ 5 . This is the first significant improvement of the bound of $$\displaystyle \tilde{O}\left( \frac{1}{\epsilon ^d}\right) $$ O ~ 1 ϵ d that was obtained in 1993 by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl for general point sets in dimension $$d\ge 3$$ d ≥ 3 .

Читать у издателя →