show/hide this revision's text 3 added 369 characters in body

Here is one relevant result, by Michael Hoffmann, "Covering polygons with few rectangles," 2001. (PDF download link)
        Hoffmann Italy
He shows that minimal covering by two or three congruent axis-aligned rectangles of a collection of polygons with a total of $n$ vertices can be found in $O(n)$ time.

He also says that the more general problem—covering a set of polygons by $p>3$ congruent rectangles—cannot be approximated by better than a factor of $2$ unless $P=NP$ (because of the relation to the $p$-center problem). He does not directly address covering just one polygon, or with covering by incongruent rectangles.

This latter problem (your problem) is partially addressed computationally in the paper 2011, "Covering a polygonal region by rectangles," Computational Optimization and Applications (Springer link). It appears that they start with a set of rectangles, and extend them until they form a cover.
show/hide this revision's text 2 added 119 characters in body

Here is one relevant result, by Michael Hoffmann, "Covering polygons with few rectangles," 2001. (PDF download link)
        Hoffmann Italy
He shows that minimal covering by two or three congruent axis-aligned rectangles of a collection of polygons with a total of $n$ vertices can be found in $O(n)$ time.

He also says that the more general problem—covering a set of polygons by $k>3$ p>3$ congruent rectangles—cannot be approximated by better than a factor of $2$ unless $P=NP$. P=NP$ (because of the relation to the $p$-center problem). He does not address directly address covering just one polygon, or with covering by incongruent rectangles.
show/hide this revision's text 1

Here is one relevant result, by Michael Hoffmann, "Covering polygons with few rectangles," 2001. (PDF download link)
        Hoffmann Italy
He shows that minimal covering by two or three axis-aligned rectangles of a collection of polygons with a total of $n$ vertices can be found in $O(n)$ time. He also says that the more general problem—covering a set of polygons by $k>3$ rectangles—cannot be approximated by better than a factor of $2$ unless $P=NP$. He does not address directly covering just one polygon.