AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER

DOI10.1142/S1793830910000486zbMath1202.68448OpenAlexW2106734202MaRDI QIDQ3560062

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

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)

Related Items (14)

Tighter estimates for \(\epsilon\)-nets for disks ⋮ ON THE DISCRETE UNIT DISK COVER PROBLEM ⋮ AN ALGORITHMIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS — WITH APPLICATIONS ⋮ Covering segments with unit squares ⋮ Unit disk cover problem in 2D ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Discrete unit square cover problem ⋮ Limits of local search: quality and efficiency ⋮ The within-strip discrete unit disk cover problem ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ An exact algorithm for a class of geometric set-cover problems ⋮ On the Discrete Unit Disk Cover Problem ⋮ Capacitated discrete unit disk cover ⋮ Line segment disk cover

Cites Work

• Improved approximation algorithms for geometric set cover
• Homogeneous 2-hop broadcast in 2D
• Optimal packing and covering in the plane are NP-complete
• Covering a set of points in multidimensional space
• 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

This page was built for publication: AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER