Near-optimal lower bounds for -nets for half-spaces and low complexity set systems

DOI10.1007/978-3-319-44479-6_21MaRDI QIDQ4604388zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A deterministic view of random sampling and its use in geometry
• A non-linear lower bound for planar epsilon-nets
• A simple proof of optimal epsilon nets
• Almost tight bounds for \(\epsilon\)-nets
• Applications of random sampling in computational geometry. II
• Epsilon nets and union complexity
• Improved approximation algorithms for geometric set cover
• Near-optimal generalisations of a theorem of Macbeath
• New existence proofs ε-nets
• On \(k\)-sets in arrangements of curves and surfaces
• On constants for cuttings in the plane
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the density of families of sets
• Small strong epsilon nets
• Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
• State of the union (of geometric objects)
• Tight lower bounds for the size of epsilon-nets
• Tighter estimates for \(\epsilon\)-nets for disks
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover via quasi-uniform sampling
• \(\epsilon\)-nets and simplex range queries

Cited in

(8)

• Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
• Explicit construction of a small epsilon-net for linear threshold functions
• A simple proof of optimal epsilon nets
• New Lower Bounds for ϵ-nets
• Practical and efficient algorithms for the geometric hitting set problem
• Tight lower bounds for the size of epsilon-nets
• On a problem of Danzer
• 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)