Geometric Hitting Sets for Disks: Theory and Practice

DOI10.1007/978-3-662-48350-3_75zbMath1467.68196OpenAlexW2294392114MaRDI QIDQ3452850

Nabil H. Mustafa, Norbert Bus, Saurabh Ray

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48350-3_75

zbMATH Keywords

computational geometryapproximation algorithmsgeometric hitting sets

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05) Approximation algorithms (68W25)

Related Items (3)

Tighter estimates for \(\epsilon\)-nets for disks ⋮ Limits of local search: quality and efficiency ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Improved results on geometric hitting set problems
• A deterministic view of random sampling and its use in geometry
• \(\epsilon\)-nets and simplex range queries
• Almost optimal set covers in finite VC-dimension
• Independent set of intersection graphs of convex objects in 2D
• New existence proofs ε-nets
• Fast approximation algorithms for a nonconvex covering problem
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers

This page was built for publication: Geometric Hitting Sets for Disks: Theory and Practice