TY - JOUR
ID - 3044
TI - A simple greedy approximation algorithm for the unit disk cover problem
JO - AUT Journal of Mathematics and Computing
JA - AJMC
LA - en
SN - 2783-2449
AU - Imanparast, Mahdi
AU - Hashemi, Seyed Naser
AD - Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
Y1 - 2020
PY - 2020
VL - 1
IS - 1
SP - 47
EP - 55
KW - computational geometry
KW - approximation algorithms
KW - unit disk cover problem
KW - facility location
DO - 10.22060/ajmc.2018.3044
N2 - 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.
UR - https://ajmc.aut.ac.ir/article_3044.html
L1 - https://ajmc.aut.ac.ir/article_3044_69fd7125903ed84f45ff4a2b2a419779.pdf
ER -