Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems
From MaRDI portal
Publication:4604388
DOI10.1007/978-3-319-44479-6_21zbMath1425.68434MaRDI QIDQ4604388
János Pach, Nabil H. Mustafa, Andrey B. Kupavskii
Publication date: 26 February 2018
Published in: A Journey Through Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-44479-6_21
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
Related Items
On a problem of Danzer, On a Problem of Danzer, Practical and efficient algorithms for the geometric hitting set problem, Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tighter estimates for \(\epsilon\)-nets for disks
- Small strong epsilon nets
- A non-linear lower bound for planar epsilon-nets
- A deterministic view of random sampling and its use in geometry
- Improved approximation algorithms for geometric set cover
- \(\epsilon\)-nets and simplex range queries
- On \(k\)-sets in arrangements of curves and surfaces
- Almost tight bounds for \(\epsilon\)-nets
- On constants for cuttings in the plane
- A simple proof of optimal epsilon nets
- Applications of random sampling in computational geometry. II
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- Weighted geometric set cover via quasi-uniform sampling
- New existence proofs ε-nets
- Tight lower bounds for the size of epsilon-nets
- Epsilon nets and union complexity
- Small-Size $\eps$-Nets for Axis-Parallel Rectangles and Boxes
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
