How to approximate a polygon with n rectangles?

Question

Is there any algorithm that can approximate the given polygon with n non overlapping rectangles that gives the maximum coverage? By maximum coverage I mean, the sum of the rectangle areas are maximized. Rectangles are not necessarily equal sized.

The polygons I am dealing are convex. If exact solution is hard/expensive to find (which I am expecting it to be), simple good heuristics are welcome too.

Edit I always thought of approximating the polygon with rectangles inside polygon, but solutions with rectangles not totally inside polygons are also fine. If that is the case, maximization of the area becomes minimization of the area.

Edit 2 I forgot to mention that these rectangles are orthogonal rectangles, i.e. aligned with axises.

Answer 1

One approach would be to create a (in the general case rectangular) bounding box for your polygon. Calculate the difference between the area of the bounding box and the area of the polygon. If the difference is small enough, you're done, if not, continue ...

Divide the box into 4 equal-sized rectangles, 2x2. Figure out which of these rectangles is entirely inside the polygon. Calculate the difference between the total area of the rectangles inside the polygon and of the polygon. If the difference is small enough you're done, if not continue ...

Divide each of the 4 rectangles into 4 sub-rectangles ... if at any stage you find that a rectangle is either fully inside or fully outside your polygon you can remove it from the list of rectangles to subdivide at the next iteration.

In other words, use a quadtree to divide the space containing your polygon and develop it to the extent necessary to meet your accuracy criteria.