\(\varepsilon\)-Mnets: Hitting geometric set systems with subsets (Q527442)

In this paper, the authors initiate the study of $\epsilon$-Mnets. For a set system $(X,\mathcal{R})$ and $\epsilon>0$, a collection $\mathcal{M}=\{X_1,\dots,X_t\}$ of subsets of $X$ is called an $\epsilon$-Mnet for $\mathcal{R}$ of size $t$ if \begin{itemize} \item $|X_i|=\Omega(\epsilon\cdot|X|)$ for each $i=1,\dots,t$ and, \item for every $R\in\mathcal{R}$ with $|R|\geq\epsilon\cdot |X|$, there exists an index $j\in\{1,\dots,t\}$ such that $X_j\subseteq R$. \end{itemize} These may be considered to be the analogs of Macbeath regions in a combinatorial setting. \par The existence of Macbeath regions in convex bodies of unit volume in $\mathbb{R}^n$ goes back to [\textit{A. M. Macbeath}, Ann. Math. (2) 56, 269--293 (1952; Zbl 0047.04903)]: for $\epsilon>0$ there are disjoint convex subsets of volume $\Theta(\epsilon)$ of any convex body of unitary volume, so that any half-space which contains $\epsilon$ volume of $K$, does also contain one of the convex subsets of $K$. \par In combinatorial geometry, a similar construction, the notion of $\epsilon$-nets has become essential. For a set system $(X,\mathcal{R})$, and a parameter $\epsilon$, an $\epsilon$-net is a set $N\subseteq X$ satisfying $N\cap R\neq\emptyset$ for any $R\in\mathcal{R}$ so that $|R|\geq\epsilon|X|$. In [\textit{D. Haussler} and \textit{E. Welzl}, Discrete Comput. Geom. 2, 127--151 (1987; Zbl 0619.68056)] the existence of $\epsilon$-nets of size $O(\frac{d}{\epsilon}\log\frac{d}{\epsilon})$ for a set-system $(X,\mathcal{R})$ with $d$ being the $VC$ dimension of $\mathcal{R}$ has been proven. \par According to the authors (in the introduction), the beginning of their work was the realization that both notions, $\epsilon$-nets and Macbeath regions are connected. \par The existence of Macbeath regions (see [\textit{H. Brönnimann} et al., Discrete Comput. Geom. 10, No. 2, 143--155 (1993; Zbl 0778.68087)]), which establishes the existence of $O(\frac{1}{\epsilon})$ regions of volume $\Theta(\epsilon V)$ so, that every half-space which contains an $\epsilon$ fraction of the volume of the convex body, contains one of the (Macbeath) regions completely, implies that one can pick $O(\frac{1}{\epsilon})$ points in a convex body of volume $V$ which hit all half-spaces which contain an $\epsilon$ fraction of the volume of the convex body. In this paper, the authors prove, among others, a strengthening of the existence result for $\epsilon$-nets for the counting measure and set of systems induced by half-spaces in $\mathbb{R}^3$, raising the question whether further results for $\epsilon$-nets can be strengthened in the same manner.