Tight lower bounds for the size of epsilon-nets

DOI10.1090/S0894-0347-2012-00759-0zbMath1268.52011arXiv1012.1240OpenAlexW1995671037WikidataQ56853083 ScholiaQ56853083MaRDI QIDQ4924064

Gábor Tardos, János Pach

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

Mathematics Subject Classification ID

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