Approximation algorithms for the unit disk cover problem in 2D and 3D

作者：Biniaz Ahmad^*; Liu Paul; Maheshwari Anil; Smid Michiel

来源：Computational Geometry-Theory and Applications, 2017, 60: 8-18.

DOI：10.1016/j.comgeo.2016.04.002

• Unit disk covering
• Unit ball covering
• Approximation algorithms

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

• 出版日期2017-1