Let
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-2/0?wchp=dGLzVlz-zSkzk)
be a set of disks of arbitrary radii in the plane, and let
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-F/0?wchp=dGLzVlz-zSkzk)
be a set of points. We study the following three problems: (i) Assuming
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-T/0?wchp=dGLzVlz-zSkzk)
contains the set of center points of disks in
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-V/0?wchp=dGLzVlz-zSkzk)
, find a minimum-cardinality subset
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-W/0?wchp=dGLzVlz-zSkzk)
of
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-X/0?wchp=dGLzVlz-zSkzk)
(if exists), such that each disk in
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-Y/0?wchp=dGLzVlz-zSkzk)
is pierced by at least
h points of
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-10/0?wchp=dGLzVlz-zSkzk)
, where
h is a given constant. We call this problem
minimum h-piercing. (ii) Assuming
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-11/0?wchp=dGLzVlz-zSkzk)
is such that for each
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-3/0?wchp=dGLzVlz-zSkzk)
there exists a point in
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-4/0?wchp=dGLzVlz-zSkzk)
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
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-8/0?wchp=dGLzVlz-zSkzk)
of
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-9/0?wchp=dGLzVlz-zSkzk)
, such that each disk in
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-B/0?wchp=dGLzVlz-zSkzk)
is pierced by at least one point of
d024ca9">![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-C/0?wchp=dGLzVlz-zSkzk)
. We call this problem
minimum discrete piercing with cores. (iii) Assuming
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-D/0?wchp=dGLzVlz-zSkzk)
is the set of center points of disks in
13d25277027d60">![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-G/0?wchp=dGLzVlz-zSkzk)
, and that each
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-H/0?wchp=dGLzVlz-zSkzk)
covers at most
l points of
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-J/0?wchp=dGLzVlz-zSkzk)
, where
l is a constant, find a minimum-cardinality subset
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-K/0?wchp=dGLzVlz-zSkzk)
of
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-M/0?wchp=dGLzVlz-zSkzk)
, such that each point of
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-N/0?wchp=dGLzVlz-zSkzk)
is covered by at least one disk of
![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-P/0?wchp=dGLzVlz-zSkzk)
. 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
d025c5">![Click to view the MathML source](http://www.sciencedirect.com/cache/MiamiImageURL/B6TYS-4N2KTB5-3-S/0?wchp=dGLzVlz-zSkzk)
).