A simple proof of optimal epsilon nets
Given a set system $(X,\mathcal{R})$ and any $Y \subseteq X$, $\mathcal{R} \vert_Y$ is defined to be $\{ Y \cap R \mid R \in \mathcal{R}\}$. The VC-dimension VC-$\dim (\mathcal{R})$ of $\mathcal{R}$ is the size of the largest $Y \subseteq X$ for which $\mathcal{R} \vert_Y =2^Y$.\par For $\varepsilon > 0$, an $\varepsilon$-net for a set system $(X,\mathcal{R})$ is a set $N \subseteq X$ such that $N \cap R \ne \emptyset$ for all $R \in \mathcal{R}$ with $\vert R\vert \geq \varepsilon \vert X\vert $.\par A set system $(X,\mathcal{R})$ has shallow-cell complexity $\varphi_{\mathcal{R}}(\cdot,\cdot)$ if for any $Y \subseteq X$, the number of subsets in $\mathcal{R}\vert_Y$ of size at most $\ell$ is $\vert Y\vert \cdot \varphi_{\mathcal{R}}(\vert Y\vert ,\ell)$.\par The size of the smallest $\varepsilon$-nets for set systems has been settled in terms of shallow-cell complexity. The authors give a short proof of this result based on the $\varepsilon$-net bound of \textit{D. Haussler} and \textit{E. Welzl} [Discrete Comput. Geom. 2, 127--151 (1987; Zbl 0619.68056)] together with the packing lemma of \textit{D. Haussler} [J. Comb. Theory, Ser. A 69, No. 2, 217--232 (1995; Zbl 0818.60005)]. More precisely, the authors prove the following. Let $(X,\mathcal{R})$, $\vert X\vert = n$, be a set system with VC-$\dim (\mathcal{R}) = d$ and shallow-cell complexity $\varphi_{\mathcal{R}}(\cdot,\cdot)$, where $\varphi_{\mathcal{R}}(\cdot,\cdot)$ is a non-decreasing function in the first variable. Then there exists an $\varepsilon$-net for $\mathcal{R}$ of size $O(\frac{1}{\varepsilon} \log \varphi(\frac{8d}{\varepsilon},24d) + \frac{d}{\varepsilon})$.
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- New Lower Bounds for ϵ-nets
- Near-optimal lower bounds for -nets for half-spaces and low complexity set systems
- Shallow packings, semialgebraic set systems, Macbeath regions, and polynomial partitioning
- Two proofs for shallow packings
- Two proofs for shallow packings
- Computing optimal \(\varepsilon\)-nets is as easy as finding an unhit set
- On the size of set systems on \([n]\) not containing weak \((r,\Delta)\)-systems
- On Extremal Set Partitions in Cartesian Product Spaces
- scientific article; zbMATH DE number 1195522
- Almost tight bounds for -nets
- The \(\varepsilon\)-\(t\)-net problem
- When are epsilon-nets small?
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- New existence proofs ε-nets
- Shallow packings, semialgebraic set systems, Macbeath regions, and polynomial partitioning
- Near-optimal lower bounds for -nets for half-spaces and low complexity set systems
- Tight lower bounds for the size of epsilon-nets
- Computing optimal \(\varepsilon\)-nets is as easy as finding an unhit set
- On a problem of Danzer
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
- Using \(\epsilon\)-nets for solving the classification problem
- Two proofs for shallow packings
- Epsilon nets and union complexity
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- Hitting sets when the shallow cell complexity is small
- Stabbing boxes with finitely many axis-parallel lines and flats
- Deterministic fault-tolerant connectivity labeling scheme
- Escaping the curse of spatial partitioning: matchings with low crossing numbers and their applications
- Two proofs for shallow packings
This page was built for publication: A simple proof of optimal epsilon nets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1715082)
