MINIMUM GEOMETRIC DISK COVER

• INSTANCE: Set $P\subseteq Z\times Z$ of points in the plane, a rational number r>0.
• SOLUTION: A set of centers $C\subseteq Q\times Q$ 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., $\vert C\vert$.

  
  

• 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 $d\ge 3$ [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].