Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
On the Discrete Unit Disk Cover Problem
verfasst von : Gautam K. Das, Robert Fraser, Alejandro Lòpez-Ortiz, Bradford G. Nickerson
Erschienen in: WALCOM: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a set
${\cal P}$
of
n
points and a set
${\cal 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
${\cal P}$
is covered by at least one disk in
${\cal D}$
or not and (ii) if so, then find a minimum cardinality subset
${\cal D}^* \subseteq {\cal D}$
such that unit disks in
${\cal D}^*$
cover all the points in
${\cal P}$
. The discrete unit disk cover problem is a geometric version of the general set cover problem which is NP-hard [14]. The general set cover problem is not approximable within
$c \log |{\cal 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
2
n
4
).