Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949138 | Computational Geometry | 2017 | 11 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ahmad Biniaz, Paul Liu, Anil Maheshwari, Michiel Smid,