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_21zbMATH Open1425.68434OpenAlexW2593690930MaRDI QIDQ4604388FDOQ4604388
Authors: Nabil H. Mustafa, János Pach, 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
Recommendations
Cites Work
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- A combinatorial problem; stability and order for models and theories in infinitary languages
- On the density of families of sets
- \(\epsilon\)-nets and simplex range queries
- Almost tight bounds for \(\epsilon\)-nets
- On constants for cuttings in the plane
- Applications of random sampling in computational geometry. II
- Tighter estimates for \(\epsilon\)-nets for disks
- Weighted geometric set cover via quasi-uniform sampling
- Near-optimal generalisations of a theorem of Macbeath
- New existence proofs ε-nets
- Small strong epsilon nets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Epsilon nets and union complexity
- Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
- A deterministic view of random sampling and its use in geometry
- A non-linear lower bound for planar epsilon-nets
- Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
- Improved approximation algorithms for geometric set cover
- State of the union (of geometric objects)
- Tight lower bounds for the size of epsilon-nets
- On \(k\)-sets in arrangements of curves and surfaces
- A simple proof of optimal epsilon nets
Cited In (8)
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- Explicit construction of a small epsilon-net for linear threshold functions
- On a problem of Danzer
- New Lower Bounds for ϵ-nets
- Practical and efficient algorithms for the geometric hitting set problem
- Tight lower bounds for the size of epsilon-nets
- A simple proof of optimal epsilon nets
- On a problem of Danzer
This page was built for publication: Near-optimal lower bounds for \(\epsilon\)-nets for half-spaces and low complexity set systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604388)
