@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 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 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}
}