A simple greedy approximation algorithm for the unit disk cover problem

Document Type : Original Article

Authors

Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

Abstract

Given a set $\mathcal P$ of $n$ points in the plane, the unit disk cover problem, which is known as an NP-hard problem, seeks to find the minimum number of unit disks that can cover all points of $\mathcal P$. We present a new $4$-approximation algorithm with running time $O(n \log n)$ for this problem. Our proposed algorithm uses a simple approach and is easy to understand and implement.

Keywords

Main Subjects

References

[1] R. J. Fowler, M. S. Paterson, S. L. Tanimoto, Optimal packing and covering in the plane are NP-complete, Information Processing Letters, 12(3) (1981) 133-137.
[2] D. S. Hochbaum, W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of ACM, 32 (1985) 130-136.
[3] T. F. Gonzalez, Covering a set of points in multidimensional space, Information Processing Letters, 40(4) (1991) 181-188.
[4] H. Bronnimann, M. T. Goodrich, Almost optimal set covers in finite VC-dimension, Discrete and Computational Geometry, 14(4) (1995) 463-479.
[5] M. Franceschetti, M. Cook, J. Bruck, A geometric theorem for approximate disk covering algorithms, Technical report, (2001).
[6] B. Fu, Z. Chen, M. Abdelguerfi, An almost linear time 2.8334-approximation algorithm for the disc covering problem, In Proceedings of the 3rd International Conference on Algorithmic Applications in Management (AAIM’07), (2007) 317-326.
[7] P. Liu, D. Lu, A fast 25/6-approximation for the minimum unit disk cover problem, CoRR, abs/1406.3838, (2014).
[8] A. Biniaz, P. Liu, A. Maheshwari, M. Smid, Approximation algorithms for the unit disk cover problem in 2D and 3D, Computational Geometry: Theory and Applications, 60 (2017) 8-18.
[9] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, Springer Berlin Heidelberg, (2008) 95-115.
AUT Journal of Mathematics and Computing
Volume 1, Issue 1
February 2020
Pages 47-55

Files

Share

How to cite

Statistics