A simple greedy approximation algorithm for the unit disk cover problem
نویسندگان
1 Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
2 Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran
doi
10.22060/ajmc.2018.3044چکیده
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.
