Reverse Rectangle Packing

Question

I have a connected shape that consists of squares put together, e.g. take a squared paper and draw a line along the existing lines that ends at its beginning and does not cross itself.

The goal is now to find an algorithm (not brute-force) that fills this shape with as few, non-overlapping rectangles as possible.

I'm looking for the optimal solution. As can be seen in the images, the naive greedy approach (take the largest rectangle) does not work.

(Optimal)

(Greedy)

My scenario is vertices reduction, but I'm sure there are other use-cases as well.

Note: This problem seems basic, but I was not able to find a solution elsewhere. Also, is this problem NP-hard?

Edit: I just realized that, in my scenario, filling the shape with as few non-overlapping triangles as possible, would give an even better result.

Answer 1

I've spend a lot of time researching this, since I asked the initial question. For the first problem (optimally filling the shape with rectangles), I've written the solution here under the header "Optimal Greedy Meshing":

http://blackflux.wordpress.com/2014/03/01/meshing-in-voxel-engines-part-2/

The complexity is actually better (faster) than for optimally triangulating a polygon without holes. The slowest part is the Hopcroft-Karp algorithm.

Treating the shape as a polygon is also discussed in the linked blog post. Note that I'm also considering holes.

Answer 2

The first problem is harder than the one with triangles; for triangles, see the algorithms in

http://en.wikipedia.org/wiki/Polygon_triangulation

which can do it without any extra vertices.