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

### MINIMUM GEOMETRIC DISK COVER

- 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., |C|.

- Good News: Admits a PTAS [234].

- Comment: There is a PTAS also for other convex objects, e.g. squares, and in d-dimensional Euclidean space for [234]. 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 [235].

  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 [234].

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