Tight lower bounds for the size of epsilon-nets
From MaRDI portal
Publication:4924064
DOI10.1090/S0894-0347-2012-00759-0zbMath1268.52011arXiv1012.1240OpenAlexW1995671037WikidataQ56853083 ScholiaQ56853083MaRDI QIDQ4924064
Publication date: 30 May 2013
Published in: Journal of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1012.1240
Transversal (matching) theory (05D15) Erd?s problems and related topics of discrete geometry (52C10)
Related Items
Sparse hop spanners for unit disk graphs, The \(\varepsilon\)-\(t\)-net problem, Polychromatic colorings of unions of geometric hypergraphs, Lower bounds for piercing and coloring boxes, On the approximability of covering points by lines and related problems, Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems, Unnamed Item, Geometric hitting set for segments of few orientations, On the number of points in general position in the plane, Piercing axis-parallel boxes, \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets, Near-linear algorithms for geometric hitting sets and set covers, An efficient container lemma, Unnamed Item, Subsampling in Smoothed Range Spaces
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space
- A new proof of the density Hales-Jewett theorem
- A non-linear lower bound for planar epsilon-nets
- Improved approximation algorithms for geometric set cover
- A density version of the Hales-Jewett theorem for \(k=3\)
- Coloring axis-parallel rectangles
- Hitting sets when the VC-dimension is small
- \(\epsilon\)-nets and simplex range queries
- Almost tight bounds for \(\epsilon\)-nets
- Reporting points in halfspaces
- A density version of the Hales-Jewett theorem
- Almost optimal set covers in finite VC-dimension
- Density Hales-Jewett and Moser numbers
- New existence proofs ε-nets
- Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
- Efficient Colored Orthogonal Range Counting
- Regularity and Positional Games
- Decomposing Coverings and the Planar Sensor Cover Problem
- Epsilon nets and union complexity
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- Tight lower bounds for the size of epsilon-nets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Indecomposable Coverings
