** Next:** Weighted Set Problems
** Up:** Covering, Hitting, and Splitting
** Previous:** MINIMUM HITTING SET
** Index**

- INSTANCE:
Set
of points in the plane, a rational number
*r>0*.
- SOLUTION:
A set of centers
in the Euclidean plane, such
that every point in
*P* will covered by a disk with radius *r* and
center in one of the points in *C*.
- MEASURE:
Cardinality of the disk cover, i.e., .

*Good News:*
Admits a PTAS [251].
*Comment:*
There is a PTAS also for other convex objects, e.g. squares, and in
*d*-dimensional Euclidean space for
[251].
Variation in which the objective is to cover a set of points on the
line by rings of given inner radius *r* and width *w*, admits a
PTAS with time complexity exponential in *r/w*, for arbitrary *r*
and *w* the problem is approximable with relative error at most 1/2
[252].
MAXIMUM GEOMETRIC SQUARE PACKING, where the objective is
to place as many squares of a given size within a region in the plane,
also admits a PTAS [251].

** Next:** Weighted Set Problems
** Up:** Covering, Hitting, and Splitting
** Previous:** MINIMUM HITTING SET
** Index**
*Viggo Kann*

*2000-03-20*