Epsilon nets and union complexity

DOI10.1145/1542362.1542366zbMath1380.68407OpenAlexW2127739958MaRDI QIDQ5370694

Kasturi R. Varadarajan

Publication date: 20 October 2017

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

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

zbMATH Keywords

approximation algorithmsset coverepsilon nets

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (13)

Tighter estimates for \(\epsilon\)-nets for disks ⋮ A PTAS for the Weighted Unit Disk Cover Problem ⋮ A Characterization of Visibility Graphs for Pseudo-polygons ⋮ Algorithms for covering multiple submodular constraints and applications ⋮ Small strong epsilon nets ⋮ Near-linear approximation algorithms for geometric hitting sets ⋮ Constant-Factor Approximation for TSP with Disks ⋮ Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems ⋮ A non-linear lower bound for planar epsilon-nets ⋮ Tight lower bounds for the size of epsilon-nets ⋮ Near-linear algorithms for geometric hitting sets and set covers ⋮ On Partial Covering For Geometric Set Systems ⋮ Unnamed Item

This page was built for publication: Epsilon nets and union complexity