Amirkabir University of Technology AUT Journal of Mathematics and Computing 2783-2449 1 1 2020 02 01 A simple greedy approximation algorithm for the unit disk cover problem 47 55 3044 10.22060/ajmc.2018.3044 EN Mahdi Imanparast Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran Seyed Naser Hashemi Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran Journal Article 2018 04 24 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. computational geometry approximation algorithms unit disk cover problem facility location https://ajmc.aut.ac.ir/article_3044_b8af7d0fbf094517781e0382102d7b27.pdf