On the discrete unit disk cover problem

DOI10.1007/978-3-642-19094-0_16MaRDI QIDQ3078392zbMATH OpenOpenAlexFDO

Authors Robert Fraser, Bradford G. Nickerson, Gautam K. Das, Alejandro Lopez-Ortiz

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

Mathematics Subject Classification ID

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

Recommendations

• On the discrete unit disk cover problem
• Covering Points by Unit Disks of Fixed Location
• 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

• A Greedy Heuristic for the Set-Covering Problem
• A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
• Almost optimal set covers in finite VC-dimension
• An improved line-separable algorithm for discrete unit disk cover
• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering a set of points in multidimensional space
• Covering Points by Unit Disks of Fixed Location
• Exact and approximation algorithms for clustering
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Improved results on geometric hitting set problems
• Optimal packing and covering in the plane are NP-complete
• The NP-completeness column: An ongoing guide
• The searching over separators strategy to solve some NP-hard problems in subexponential time

Cited in

(30)

• Two optimization problems for unit disks
• Experiments with unit disk cover algorithms for covering massive pointsets
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• Approximation algorithm for sweep coverage on graph
• Solving energy issues for sweep coverage in wireless sensor networks
• A note on minimum-sum coverage by aligned disks
• Discretely following a curve
• APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS
• Following a curve with the discrete Fréchet distance
• The approximation algorithms for a class of multiple-choice problem
• A PTAS for the Weighted Unit Disk Cover Problem
• An improved line-separable algorithm for discrete unit disk cover
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• Discrete unit square cover problem
• Unit disk cover problem in 2D
• A constant-factor approximation for multi-covering with disks
• The within-strip discrete unit disk cover problem
• On the discrete unit disk cover problem
• Covering Points by Unit Disks of Fixed Location
• Covering Many or Few Points with Unit Disks
• Algorithms for the line-constrained disk coverage and related problems
• A constant-factor approximation algorithm for red-blue set cover with unit disks
• Algorithms for the line-constrained disk coverage and related problems
• Capacitated discrete unit disk cover
• A constant-factor approximation algorithm for red-blue set cover with unit disks
• On the geometric priority set cover problem
• Polynomial time approximation schemes for minimum disk cover problems
• Approximation algorithms for the unit disk cover problem in 2D and 3D
• The subinterval cover problem
• Covering many or few points with unit disks

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 Q3078392)