- INSTANCE:
An arbitrary polygon
*P*. - 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].*Garey and Johnson:*SR25