On the Discrete Unit Disk Cover Problem
From MaRDI portal
Publication:3078392
DOI10.1007/978-3-642-19094-0_16zbMath1317.68273OpenAlexW2154260184MaRDI QIDQ3078392
Bradford G. Nickerson, Robert Fraser, Alejandro López-Ortiz, Gautam K. Das
Publication date: 20 February 2011
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-19094-0_16
Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items
Following a curve with the discrete Fréchet distance ⋮ The approximation algorithms for a class of multiple-choice problem ⋮ On the geometric priority set cover problem ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Discretely Following a Curve ⋮ Approximation algorithm for sweep coverage on graph ⋮ Solving energy issues for sweep coverage in wireless sensor networks
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved results on geometric hitting set problems
- Optimal packing and covering in the plane are NP-complete
- Covering a set of points in multidimensional space
- Exact and approximation algorithms for clustering
- Almost optimal set covers in finite VC-dimension
- The searching over separators strategy to solve some NP-hard problems in subexponential time
- AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER
- Approximation schemes for covering and packing problems in image processing and VLSI
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Greedy Heuristic for the Set-Covering Problem
- Covering Points by Unit Disks of Fixed Location
- The NP-completeness column: An ongoing guide