New Lower Bounds for ϵ-nets

DOI10.4230/LIPICS.SOCG.2016.54zbMATH Open1390.68721OpenAlexW2538756287MaRDI QIDQ3132890FDOQ3132890

Authors: Nabil H. Mustafa, János Pach, Andrey B. Kupavskii 

Publication date: 30 January 2018

Full work available at URL: https://hal.science/hal-01345861

Recommendations

• Almost tight bounds for \(\epsilon\)-nets
• Tight lower bounds for the size of epsilon-nets
• Tight lower bounds for the size of epsilon-nets
• Near-optimal lower bounds for \(\epsilon\)-nets for half-spaces and low complexity set systems
• New existence proofs ε-nets
• New constructions of weak \(\varepsilon\)-nets
• Improved bounds on weak \(\varepsilon\)-nets for convex sets
• A lower bound for weak \(\varepsilon\)-nets in high dimension
• Lower bounds for weak epsilon-nets and stair-convexity
• Lower bounds for weak epsilon-nets and stair-convexity

zbMATH Keywords

lower boundsgeometric set systemsshallow-cell complexity\(\varepsilon\)-netshalf-spaces

Mathematics Subject Classification ID

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

Cited In (18)

• Title not available (Why is that?)
• Explicit construction of a small \(\epsilon\)-net for linear threshold functions
• Stronger bounds for weak epsilon-nets in higher dimensions
• Near-optimal generalisations of a theorem of Macbeath
• A lower bound for weak \(\varepsilon\)-nets in high dimension
• Weak \(\varepsilon \)-nets have basis of size \(O(1/\varepsilon\log (1/\varepsilon))\) in any dimension
• The \(\varepsilon\)-\(t\)-net problem
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Stabbing boxes with finitely many axis-parallel lines and flats
• New existence proofs ε-nets
• Near-linear algorithms for geometric hitting sets and set covers
• When are epsilon-nets small?
• Tight lower bounds on the VC-dimension of geometric set systems
• Tight lower bounds for the size of epsilon-nets
• Tight lower bounds for the size of epsilon-nets
• Near-optimal lower bounds for \(\epsilon\)-nets for half-spaces and low complexity set systems
• A simple proof of optimal epsilon nets
• \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets

This page was built for publication: New Lower Bounds for ϵ-nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132890)