Epsilon nets and union complexity

DOI10.1145/1542362.1542366MaRDI QIDQ5370694zbMATH OpenOpenAlexFDO

Authors Kasturi 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 algorithmsepsilon netsset cover

Mathematics Subject Classification ID

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

Recommendations

• Tight lower bounds for the size of epsilon-nets
• Tight lower bounds for the size of epsilon-nets
• Almost tight bounds for -nets
• The complexity of unions of disjoint sets
• The Complexity of Unions of Disjoint Sets
• The epsilon calculus and Herbrand complexity
• Construction of \(\epsilon\)-nets
• Union-freeness, deterministic union-freeness and union-complexity
• A simple proof of optimal epsilon nets
• scientific article; zbMATH DE number 431986

Cited in

(18)

• Algorithms for covering multiple submodular constraints and applications
• Near-linear algorithms for geometric hitting sets and set covers
• Near-linear approximation algorithms for geometric hitting sets
• Tighter estimates for -nets for disks
• A PTAS for the Weighted Unit Disk Cover Problem
• A characterization of visibility graphs for pseudo-polygons
• Small strong epsilon nets
• Constant-factor approximation for TSP with disks
• Near-optimal lower bounds for -nets for half-spaces and low complexity set systems
• Tight lower bounds for the size of epsilon-nets
• On partial covering for geometric set systems
• Small-size -nets for axis-parallel rectangles and boxes
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Helly-type theorems for approximate covering
• A bicriteria approximation algorithm for the minimum hitting set problem in measurable range spaces
• Hitting sets when the shallow cell complexity is small
• A non-linear lower bound for planar epsilon-nets
• Construction of \(\epsilon\)-nets

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

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