Covering Points by Unit Disks of Fixed Location

DOI10.1007/978-3-540-77120-3_56zbMath1193.68268OpenAlexW1539563432MaRDI QIDQ5387798

Paz Carmi, Nissan Lev-Tov, Matthew J. Katz

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_56

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15) Approximation algorithms (68W25)

Related Items

Tighter estimates for \(\epsilon\)-nets for disks ⋮ A Scheme for Computing Minimum Covers within Simple Regions ⋮ Improved results on geometric hitting set problems ⋮ Covering moving points with anchored disks ⋮ A scheme for computing minimum covers within simple regions ⋮ Unit disk cover problem in 2D ⋮ Discrete unit square cover problem ⋮ Limits of local search: quality and efficiency ⋮ The within-strip discrete unit disk cover problem ⋮ Minimizing the total cost of barrier coverage in a linear domain ⋮ An exact algorithm for a class of geometric set-cover problems ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ On the Discrete Unit Disk Cover Problem ⋮ Capacitated discrete unit disk cover ⋮ Line segment disk cover ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Homogeneous 2-hop broadcast in 2D ⋮ On interval and circular-arc covering problems

Cites Work

• Unnamed Item
• Covering a set of points in multidimensional space
• Almost optimal set covers in finite VC-dimension
• Approximation schemes for covering and packing problems in image processing and VLSI
• Improved approximation algorithms for geometric set cover
• The NP-completeness column: An ongoing guide