SOLUTION:
A collection of m rectangles whose union is exactly
equal to the polygon P.
MEASURE:
Size, i.e. number m of elements, of the collection.
Good News:
Approximable within ,
where n
denotes the number of vertices of the polygon [351].
Comment: If the vertices are given as polynomially bounded integer
coordinates, then the problem is approximable within
[207]. In the case of rectilinear polygons with holes, the
rectangular covering is APX-hard [74]. If the solution
can contain only squares, then the problem is approximable within 14
[352].
,
where n
denotes the number of vertices of the polygon [351].
[207]. In the case of rectilinear polygons with holes, the
rectangular covering is APX-hard [74]. If the solution
can contain only squares, then the problem is approximable within 14
[352].