Practical Discrete Unit Disk Cover Using an Exact Line-Separable Algorithm
[.pdf]
Abstract
Given m unit disks and n points in the plane,
the discrete unit disk cover problem is to select a minimum subset of the
disks to cover the points.
This problem is NP-hard [Johnson 1982] and
the best previous practical solution is a
38-approximation algorithm by Carmi et al. [Carmi 2007].
We first consider the line-separable discrete unit disk cover problem
(the set of disk centres can be separated from the set of points by a line)
for which we present an O(m
2n)-time algorithm that finds an exact solution.
Combining our line-separable algorithm with
techniques from the algorithm of Carmi et al. [Carmi 2007]
results in an O(m
2n
4) time 22-approximate solution to the
discrete unit disk cover problem.
Bibtex Entry
