A simple greedy approximation algorithm for the unit disk cover problem

Document Type : Original Article


Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran


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. In this paper, we present a new 4-approximation algorithm with running time O(n log n) for this problem. Our proposed algorithm uses a simple greedy approach and is easy to understand and implement.


Main Subjects