A simple greedy approximation algorithm for the unit disk cover problem
Mahdi Imanparast, Seyed Naser Hashemi · DOAJ (DOAJ: Directory of Open Access Journals) · 2018
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.