New existence proofs ε-nets

DOI10.1145/1377676.1377708zbMATH Open1221.52016OpenAlexW1975581100MaRDI QIDQ3602913FDOQ3602913

Evangelia Pyrga, Saurabh Ray

Publication date: 12 February 2009

Published in: Proceedings of the twenty-fourth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1377676.1377708

Recommendations

• The \(\varepsilon\)-\(t\)-net problem
• 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

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Hypergraphs (05C65)

Cited In (30)

• Tighter estimates for \(\epsilon\)-nets for disks
• Small strong epsilon nets
• Improved results on geometric hitting set problems
• Improved bounds on the Hadwiger-Debrunner numbers
• A simple proof of the shallow packing lemma
• Packing and covering with non-piercing regions
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Piercing axis-parallel boxes
• Approximation algorithms for maximum independent set of pseudo-disks
• Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems
• Local search strikes again: PTAS for variants of geometric covering and packing
• A non-linear lower bound for planar epsilon-nets
• New Lower Bounds for ϵ-nets
• The \(\varepsilon\)-\(t\)-net problem
• A PTAS for the Weighted Unit Disk Cover Problem
• Constructing planar support for non-piercing regions
• Title not available (Why is that?)
• Existence of planar support for geometric hypergraphs using elementary techniques
• Practical and efficient algorithms for the geometric hitting set problem
• Subsampling in Smoothed Range Spaces
• Construction of \(\epsilon\)-nets
• Geometric Hitting Sets for Disks: Theory and Practice
• Planar Support for Non-piercing Regions and Applications
• Approximation algorithms for the connected sensor cover problem
• Near-linear algorithms for geometric hitting sets and set covers
• On Desarguesian extensions of elation nets
• Tight lower bounds for the size of epsilon-nets
• \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets
• The within-strip discrete unit disk cover problem
• Near-linear approximation algorithms for geometric hitting sets

This page was built for publication: New existence proofs ε-nets

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