A non-linear lower bound for planar epsilon-nets
From MaRDI portal
Publication:664354
DOI10.1007/s00454-010-9323-7zbMath1232.68161OpenAlexW2124187705MaRDI QIDQ664354
Publication date: 1 March 2012
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00454-010-9323-7
Related Items
Uniformly Discrete Forests with Poor Visibility ⋮ Unsplittable coverings in the plane ⋮ Small strong epsilon nets ⋮ A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space ⋮ 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 ⋮ On weak \(\epsilon\)-nets and the Radon number ⋮ Geometric hitting set for segments of few orientations ⋮ On the number of points in general position in the plane ⋮ Lower bounds for weak epsilon-nets and stair-convexity ⋮ Tight lower bounds for the size of epsilon-nets ⋮ Unnamed Item ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ An efficient container lemma
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new proof of the density Hales-Jewett theorem
- Lower bounds for weak epsilon-nets and stair-convexity
- Improved approximation for guarding simple galleries from the perimeter
- A deterministic view of random sampling and its use in geometry
- Improved approximation algorithms for geometric set cover
- A density version of the Hales-Jewett theorem for \(k=3\)
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Partitioning arrangements of lines. II: Applications
- Hitting sets when the VC-dimension is small
- \(\epsilon\)-nets and simplex range queries
- Almost tight bounds for \(\epsilon\)-nets
- Reporting points in halfspaces
- Improved bounds on weak \(\varepsilon\)-nets for convex sets
- New constructions of weak \(\varepsilon\)-nets
- A density version of the Hales-Jewett theorem
- New applications of random sampling in computational geometry
- Transversal numbers for hypergraphs arising in geometry
- Almost optimal set covers in finite VC-dimension
- Density Hales-Jewett and Moser numbers
- New existence proofs ε-nets
- Regularity and Positional Games
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Point Selections and Weak ε-Nets for Convex Hulls
- Small-size ε-nets for axis-parallel rectangles and boxes
- Epsilon nets and union complexity
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Indecomposable Coverings
