A simple greedy approximation algorithm for the unit disk cover problem

Document Type : Original Article

Authors

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

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. 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.

Keywords

Main Subjects