An improved line-separable algorithm for discrete unit disk cover

DOI10.1142/S1793830910000486MaRDI QIDQ3560062zbMATH OpenOpenAlexFDO

Authors Francisco Claude, Reza Dorrigiv, Stephane Durocher, Robert Fraser, Bradford G. Nickerson, Alejandro Salinger, Gautam K. Das, Alejandro Lopez-Ortiz

Publication date 19 May 2010

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s1793830910000486

zbMATH Keywords

approximation algorithmdiscrete unit disk coverdisk stabbing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• Unit disk cover problem in 2D
• On the discrete unit disk cover problem
• On the discrete unit disk cover problem
• Covering Points by Unit Disks of Fixed Location

Cites work

• Approximation schemes for covering and packing problems in image processing and VLSI
• Covering a set of points in multidimensional space
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Homogeneous 2-hop broadcast in 2D
• Improved approximation algorithms for geometric set cover
• Optimal packing and covering in the plane are NP-complete
• The NP-completeness column: An ongoing guide

Cited in

(25)

• An exact algorithm for a class of geometric set-cover problems
• Tighter estimates for -nets for disks
• An algorithmic framework for solving geometric covering problems -- with applications
• On the discrete unit disk cover problem
• Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
• Discrete unit square cover problem
• 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
• Covering Points by Unit Disks of Fixed Location
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• 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
• Line segment disk cover
• On the line-separable unit-disk coverage and related problems
• Approximation algorithms for minimum ply covering of points with unit squares and unit disks
• Approximation algorithms for the unit disk cover problem in 2D and 3D
• Algorithms for halfplane coverage and related problems
• On the line-separable unit-disk coverage and related problems
• On line-separable weighted unit-disk coverage and related problems
• Unweighted geometric hitting set for line-constrained disks and related problems
• On line-separable weighted unit-disk coverage and related problems
• Algorithms for halfplane coverage and related problems

This page was built for publication: An improved line-separable algorithm for discrete unit disk cover

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