On the Discrete Unit Disk Cover Problem
[.pdf]
Abstract
Given a set P of n points and a set D of m unit
disks on a 2-dimensional plane, the discrete unit disk cover (DUDC)
problem is (i) to check whether each point in P is covered
by at least one disk in D or not and (ii) if so, then find a
minimum cardinality subset D
* \subseteq D such that
unit disks in D
* cover all the points in P. The
discrete unit disk cover problem is a geometric version of the general set
cover problem which is NP-hard [Johnson82]. The general set cover
problem is not approximable within c log |P|, for some
constant c, but the DUDC problem was shown to admit a constant
factor approximation. In this paper, we provide an algorithm with
constant approximation factor 18. The running time of the proposed
algorithm is O(n log n + m log m + mn). The previous best known
tractable solution for the same problem was a 22-factor approximation algorithm
with running time O(m
2n
4).
Bibtex Entry
