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.

Additional Metadata
Conference 27th Canadian Conference on Computational Geometry, CCCG 2015
Citation
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).