Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions

Abstract

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|\ge \epsilon |P|$. We show that for any finite point set in dimension $d\ge 3$, and any $\epsilon >0$, one can construct a weak $\epsilon$-net whose cardinality is $O^{\ast }\left(\frac{1}{{\epsilon }^{2.558}}\right)$ in dimension $d=3$, and $o\left(\frac{1}{{\epsilon }^{d-1/2}}\right)$ in all dimensions $d\ge 4$. To be precise, our weak $\epsilon$-net has cardinality $O\left(\frac{1}{{\epsilon }^{{\alpha }_d+\gamma }}\right)$ for any $\gamma >0$, with $${\alpha }_d=\left\{\begin{array}{lc}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\}$$ This is the first significant improvement of the bound of $\tilde{O}\left(\frac{1}{{\epsilon }^d}\right)$ that was obtained in 1993 by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl for general point sets in dimension $d\ge 3$.

Preliminary version accepted to STOC 2021. The exponent is corrected in dimension 3, and slightly improved in all dimensions $d\ge 4$. Submitted to a journal