Let
be a set of disks of arbitrary radii in the plane, and let
be a set of points. We study the following three problems: (i) Assuming
contains the set of center points of disks in
, find a minimum-cardinality subset
of
(if exists), such that each disk in
is pierced by at least
h points of
, where
h is a given constant. We call this problem
minimum h-piercing. (ii) Assuming
is such that for each
there exists a point in
whose distance from
D's center is at most
αr(
D), where
r(
D) is
D's radius and 0
α<1 is a given constant, find a minimum-cardinality subset
of
, such that each disk in
is pierced by at least one point of
. We call this problem
minimum discrete piercing with cores. (iii) Assuming
is the set of center points of disks in
, and that each
covers at most
l points of
, where
l is a constant, find a minimum-cardinality subset
of
, such that each point of
is covered by at least one disk of
. We call this problem
minimum center covering. For each of these problems we present a constant-factor approximation algorithm (trivial for problem (iii)), followed by a polynomial-time approximation scheme. The polynomial-time approximation schemes are based on an adapted and extended version of Chan's [T.M. Chan, Polynomial-time approximation schemes for packing and piercing fat objects, J. Algorithms 46 (2003) 178–189] separator theorem. Our PTAS for problem (ii) enables one, in practical cases, to obtain a (1+
ε)-approximation for minimum discrete piercing (i.e., for arbitrary
).
相似文献