Name
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 ( n log ź n ) -time. We also show how to extend this algorithm to other metrics, and to three dimensions. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.comgeo.2016.04.002 | Comput. Geom. |
Keywords | Field | DocType |
Unit disk covering,Unit ball covering,Approximation algorithms | Discrete mathematics,Approximation algorithm,Combinatorics,Unit disk,Mathematics | Journal |
Volume | Issue | ISSN |
60 | C | 0925-7721 |
Citations | PageRank | References |
6 | 0.46 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ahmad Biniaz | 1 | 44 | 20.67 |
| Paul Liu | 2 | 23 | 6.59 |
| Anil Maheshwari | 3 | 869 | 104.47 |
| Michiel H. M. Smid | 4 | 550 | 93.58 |