@article {
author = {Imanparast, Mahdi and Hashemi, Seyed Naser},
title = {A simple greedy approximation algorithm for the unit disk cover problem},
journal = {AUT Journal of Mathematics and Computing},
volume = {1},
number = {1},
pages = {47-55},
year = {2020},
publisher = {Amirkabir University of Technology},
issn = {2783-2449},
eissn = {2783-2287},
doi = {10.22060/ajmc.2018.3044},
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 = {computational geometry,approximation algorithms,unit disk cover problem,facility location},
url = {https://ajmc.aut.ac.ir/article_3044.html},
eprint = {https://ajmc.aut.ac.ir/article_3044_69fd7125903ed84f45ff4a2b2a419779.pdf}
}