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(nlog n)-time. We also show how to extend this algorithm to other metrics, and to three dimensions.

Additional Metadata
Keywords Approximation algorithms, Unit ball covering, Unit disk covering
Persistent URL
Journal Computational Geometry
Biniaz, A. (Ahmad), Liu, P. (Paul), Maheshwari, A, & Smid, M. (2017). Approximation algorithms for the unit disk cover problem in 2D and 3D. Computational Geometry, 60, 8–18. doi:10.1016/j.comgeo.2016.04.002