Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems

DOI10.1007/978-3-319-44479-6_21zbMath1425.68434OpenAlexW2593690930MaRDI 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

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning, Practical and efficient algorithms for the geometric hitting set problem, On a problem of Danzer, On a Problem of Danzer

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