MINIMUM RECTANGLE COVER

• 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 $O(n\log n)$, 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 $O(\log n)$ [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