Covering Points by Unit Disks of Fixed Location

DOI10.1007/978-3-540-77120-3_56MaRDI QIDQ5387798zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On the discrete unit disk cover problem
• On the discrete unit disk cover problem
• Unit disk cover problem in 2D
• An improved line-separable algorithm for discrete unit disk cover
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm

Cites work

• Almost optimal set covers in finite VC-dimension
• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering a set of points in multidimensional space
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Improved approximation algorithms for geometric set cover
• The NP-completeness column: An ongoing guide

Cited in

(42)

• Homogeneous 2-hop broadcast in 2D
• Identification of points using disks
• Fuzzy disk for covering fuzzy points
• An exact algorithm for a class of geometric set-cover problems
• On interval and circular-arc covering problems
• Covering a Euclidean line or hyperplane by dilations of its discretization
• A scheme for computing minimum covers within simple regions
• Polynomial-time approximation schemes for piercing and covering with applications in wireless networks
• Tighter estimates for -nets for disks
• A constant-factor approximation for multi-covering with disks
• On isolating points using unit disks
• On the discrete unit disk cover problem
• On Isolating Points Using Disks
• Covering Discs in Minkowski Planes
• A Scheme for Computing Minimum Covers within Simple Regions
• An improved line-separable algorithm for discrete unit disk cover
• Minimum-cost coverage of point sets by disks
• Covering moving points with anchored disks
• Discrete unit square cover problem
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• Unit disk cover problem in 2D
• Limits of local search: quality and efficiency
• The within-strip discrete unit disk cover problem
• On the discrete unit disk cover problem
• Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
• Covering Many or Few Points with Unit Disks
• A constant-factor approximation algorithm for red-blue set cover with unit disks
• Capacitated discrete unit disk cover
• Line segment disk cover
• Capacitated discrete unit disk cover
• A constant-factor approximation algorithm for red-blue set cover with unit disks
• Improved results on geometric hitting set problems
• On the line-separable unit-disk coverage and related problems
• Worst-case optimal covering of rectangles by disks
• Approximation algorithms for minimum ply covering of points with unit squares and unit disks
• Algorithms for halfplane coverage and related problems
• Worst-case optimal covering of triangles by disks
• On the line-separable unit-disk coverage and related problems
• Minimizing the total cost of barrier coverage in a linear domain
• Algorithms for halfplane coverage and related problems
• Minimum ply covering of points with disks and squares
• Covering many or few points with unit disks

This page was built for publication: Covering Points by Unit Disks of Fixed Location

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