On the discrete unit disk cover problem
DOI10.1142/S0218195912500094zbMATH Open1267.68267MaRDI QIDQ5300002FDOQ5300002
Authors: Robert Fraser, Bradford G. Nickerson, Gautam K. Das, Alejandro Lopez-Ortiz 
Publication date: 24 June 2013
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Recommendations
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial complexity of geometric structures (52C45) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)
Cites Work
- A Greedy Heuristic for the Set-Covering Problem
- Almost optimal set covers in finite VC-dimension
- An improved line-separable algorithm for discrete unit disk cover
- Improved results on geometric hitting set problems
- Exact and approximation algorithms for clustering
- Approximation schemes for covering and packing problems in image processing and VLSI
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- The NP-completeness column: An ongoing guide
- The searching over separators strategy to solve some NP-hard problems in subexponential time
- Optimal packing and covering in the plane are NP-complete
- Covering a set of points in multidimensional space
Cited In (29)
- Line segment disk cover
- Approximation algorithms for the unit disk cover problem in 2D and 3D
- Algorithms for the line-constrained disk coverage and related problems
- Algorithms for the line-constrained disk coverage and related problems
- Capacitated discrete unit disk cover
- Capacitated discrete unit disk cover
- Tighter estimates for \(\epsilon\)-nets for disks
- Covering Points by Unit Disks of Fixed Location
- Covering many or few points with unit disks
- A 4.31-approximation for the geometric unique coverage problem on unit disks
- Discrete unit square cover problem
- Identification of points using disks
- Unit disk cover problem in 2D
- An improved line-separable algorithm for discrete unit disk cover
- Parallel algorithm for minimum partial dominating set in unit disk graph
- Minimum dominating set problem for unit disks revisited
- A PTAS for the Weighted Unit Disk Cover Problem
- Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
- On the discrete unit disk cover problem
- Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
- Covering Many or Few Points with Unit Disks
- Approximation algorithms for minimum ply covering of points with unit squares and unit disks
- A constant-factor approximation for multi-covering with disks
- Two optimization problems for unit disks
- APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
- Experiments with unit disk cover algorithms for covering massive pointsets
- An exact algorithm for a class of geometric set-cover problems
- Limits of local search: quality and efficiency
- The within-strip discrete unit disk cover problem
This page was built for publication: On the discrete unit disk cover problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300002)
