A simple proof of optimal epsilon nets

DOI10.1007/s00493-017-3564-5zbMath1424.52020OpenAlexW2587329907MaRDI QIDQ1715082

Nabil H. Mustafa, Kunal Dutta, Arijit Ghosh

Publication date: 1 February 2019

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00493-017-3564-5

zbMATH Keywords

VC-dimensionset systemshallow-cell complexity$\varepsilon$-net

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Transversal (matching) theory (05D15) Combinatorial complexity of geometric structures (52C45)

Related Items (6)

Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ Unnamed Item ⋮ When are epsilon-nets small? ⋮ On a Problem of Danzer ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg

This page was built for publication: A simple proof of optimal epsilon nets