A faster 4-approximation algorithm for the unit disk cover problem
Given a set P of n points in the plane, we consider the problem of covering P with a minimum number of unit disks. This problem is known to be NP-hard. We present a simple 4-approximation algorithm for this problem which runs in O(n log n)-time and uses the plane-sweep technique. Previous algorithms that achieve the same approximation ratio have a higher time complexity. We also show how to extend this algorithm to other metrics, and to three dimensions.
|Conference||27th Canadian Conference on Computational Geometry, CCCG 2015|
Biniaz, A. (Ahmad), Liu, P. (Paul), Maheshwari, A, & Smid, M. (2015). A faster 4-approximation algorithm for the unit disk cover problem. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015 (pp. 262–267).