of points in the plane, a rational number
r>0
.
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
.
[
169
].
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
[
170
].
The Maximum Geometric Square Packing Problem , where the objective is to place as many squares of a given size within a region in the plane, also admits a PTAS [ 169 ].
Viggo Kann