AN IMPROVED LINE-SEPARABLE ALGORITHM FOR DISCRETE UNIT DISK COVER

DOI10.1142/S1793830910000486zbMath1202.68448MaRDI 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)

zbMATH Keywords

approximation algorithm; discrete unit disk cover; disk stabbing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W25: Approximation algorithms

Related Items

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

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