Tight lower bounds for the size of epsilon-nets

DOI10.1090/S0894-0347-2012-00759-0MaRDI QIDQ4924064zbMATH OpenOpenAlexWikidataFDO

Authors János Pach, Gábor Tardos

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)

Abstract: According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an $eps$-net of size $Oleft(frac1epslogfrac1epsight)$. Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range spaces of VC-dimension 2, for which the above bound can be attained. The only known range spaces of small VC-dimension, in which the ranges are geometric objects in some Euclidean space and the size of the smallest $eps$-nets is superlinear in $frac1eps$, were found by Alon (2010). In his examples, the size of the smallest $eps$-nets is $Omegaleft(frac1epsg(frac1eps)ight)$, where $g$ is an extremely slowly growing function, closely related to the inverse Ackermann function. smallskip We show that there exist geometrically defined range spaces, already of VC-dimension $2$, in which the size of the smallest $eps$-nets is $Omegaleft(frac1epslogfrac1epsight)$. We also construct range spaces induced by axis-parallel rectangles in the plane, in which the size of the smallest $eps$-nets is $Omegaleft(frac1epsloglogfrac1epsight)$. By a theorem of Aronov, Ezra, and Sharir (2010), this bound is tight.

Recommendations

• Tight lower bounds for the size of epsilon-nets
• Almost tight bounds for -nets
• A non-linear lower bound for planar epsilon-nets
• New Lower Bounds for ϵ-nets
• A simple proof of optimal epsilon nets

Cites work

• -nets and simplex range queries
• A density version of the Hales-Jewett theorem
• A density version of the Hales-Jewett theorem for \(k=3\)
• A new proof of the density Hales-Jewett theorem
• A non-linear lower bound for planar epsilon-nets
• A note about weak -nets for axis-parallel boxes in d-space
• Almost optimal set covers in finite VC-dimension
• Almost tight bounds for -nets
• Coloring axis-parallel rectangles
• Decomposing coverings and the planar sensor cover problem
• Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
• Density Hales-Jewett and Moser numbers
• Efficient Colored Orthogonal Range Counting
• Epsilon nets and union complexity
• Hitting sets when the VC-dimension is small
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• Improved approximation algorithms for geometric set cover
• Improved bound for the union of fat triangles
• Indecomposable Coverings
• New existence proofs ε-nets
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Regularity and Positional Games
• Reporting points in halfspaces
• Small-size -nets for axis-parallel rectangles and boxes
• Tight lower bounds for the size of epsilon-nets

Cited in

(30)

• Almost tight bounds for -nets
• Piercing axis-parallel boxes
• The \(\varepsilon\)-\(t\)-net problem
• Near-linear algorithms for geometric hitting sets and set covers
• When are epsilon-nets small?
• Weak -nets have basis of size O(1/ (1/)) in any dimension
• Subsampling in smoothed range spaces
• New Lower Bounds for ϵ-nets
• scientific article; zbMATH DE number 431986 (Why is no real title available?)
• New existence proofs ε-nets
• Near-optimal lower bounds for -nets for half-spaces and low complexity set systems
• On the number of points in general position in the plane
• An efficient container lemma
• \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets
• Epsilon nets and union complexity
• Tight lower bounds on the VC-dimension of geometric set systems
• Small-size -nets for axis-parallel rectangles and boxes
• Explicit construction of a small -net for linear threshold functions
• Tight lower bounds for the size of epsilon-nets
• Polychromatic colorings of unions of geometric hypergraphs
• Stronger bounds for weak epsilon-nets in higher dimensions
• scientific article; zbMATH DE number 7765415 (Why is no real title available?)
• Lower bounds for piercing and coloring boxes
• The complexity of recognizing geometric hypergraphs
• A non-linear lower bound for planar epsilon-nets
• Stabbing boxes with finitely many axis-parallel lines and flats
• The complexity of recognizing geometric hypergraphs
• Stabbing convex bodies with lines and flats
• Sparse hop spanners for unit disk graphs
• On the approximability of covering points by lines and related problems

This page was built for publication: Tight lower bounds for the size of epsilon-nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4924064)