Title of article :
A simple greedy approximation algorithm for the unit disk cover problem
Author/Authors :
Imanparast, Mahdi Department of Mathematics and Computer Science - Amirkabir University of Technology, Tehran, Iran , Hashemi, Naser 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. 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.
Keywords :
Computational geometry , Approximation algorithms , Unit disk cover problem , Facility location
Journal title :
AUT Journal of Mathematics and Computing
