New existence proofs ε-nets

DOI10.1145/1377676.1377708MaRDI QIDQ3602913zbMATH OpenOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

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

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

Cited in

(30)

• Near-linear approximation algorithms for geometric hitting sets
• Tighter estimates for -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)
• On hypergraph supports (extended abstract)
• Piercing axis-parallel boxes
• Approximation algorithms for maximum independent set of pseudo-disks
• Geometric hitting sets for disks: theory and practice
• Subsampling in smoothed range spaces
• A non-linear lower bound for planar epsilon-nets
• Local search strikes again: PTAS for variants of geometric covering and packing
• New Lower Bounds for ϵ-nets
• The \(\varepsilon\)-\(t\)-net problem
• Constructing planar support for non-piercing regions
• A PTAS for the Weighted Unit Disk Cover Problem
• scientific article; zbMATH DE number 3842635 (Why is no real title available?)
• Practical and efficient algorithms for the geometric hitting set problem
• Existence of planar support for geometric hypergraphs using elementary techniques
• Construction of \(\epsilon\)-nets
• Planar Support for Non-piercing Regions and Applications
• 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
• Near-optimal lower bounds for \(\epsilon\)-nets for half-spaces and low complexity set systems
• \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets
• The within-strip discrete unit disk cover problem

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)