Approximation algorithms for the unit disk cover problem in 2D and 3D
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.
|Keywords||Approximation algorithms, Unit ball covering, Unit disk covering|
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