Article ID Journal Published Year Pages File Type
4949138 Computational Geometry 2017 11 Pages PDF
Abstract
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.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,