Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

Given a contiguous subset of a chessboard (or, more general, a 2d rectangular grid), how can I algorithmically determine a minimal set of rectangles covering the area?

enter image description here

In this example, the "contiguous subset" is the black area, and I am interested in the three red rectangles. There should be no overlap between the rectangles. The relative sizes of the rectangles is not too important; it would be a bonus if the sizes weren't too different.

share|improve this question

marked as duplicate by Rahul, Behaviour, William, amWhy, Adam Hughes Sep 3 at 22:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
That is a cool picture. –  Stefan Smith May 25 '13 at 20:13
2  
So you could extend the single square horizontally to give rectangles of areas 3, 4 and 6 - which would be a "better" solution according to your criteria - and illustrates an issue about obtaining an algorithm - it isn't necessarily best to lop off the bits which protrude. –  Mark Bennet May 25 '13 at 21:38
    
Incidentally, the converse of this question has been explored a fair bit. Googling about 'tiling rectangles with polyominoes' should provide plenty of information about this latter question. –  Benjamin Dickman May 26 '13 at 0:47
    
@StefanSmith Thanks :) I put the SVG source of the pic here, in case you're interested: gist.github.com/andreas-h/5970117 –  andreas-h Jul 10 '13 at 20:40
    
@andreas-h Thanks. It looks like you put a lot of work into it, though I would guess there was some cut-and-pasting involved. –  Stefan Smith Jul 20 '13 at 18:35

1 Answer 1

If the problem is that small, you can use brute-force search: list all rectangles contained in the area, list all sets of rectangles, keep those that partition the area, and select the best one.

To reduce the number of candidates, you can arrange non-overlapping sets of rectangles into a tree (the root is the empty set, each level adds one rectangle, the partitions are among the leaves). In your implementation, you do not need to store the tree, you just have to explore it.

If the problem is larger, instead of all rectangles, you can use the maximal rectangles, their intersections and differences.

If an approximate solution is acceptable, you can start with a partition into rectangles (say, all $1\times1$ rectangles), grow those rectangles as much as possible (in random directions), remove or cut them (at random) to have a partition. Iterate many times and keep the best solution. I think a similar algorithm is used to simplify boolean expressions (but overlaps are allowed).

share|improve this answer
    
the problem is large, about 3000x6000. and the solution needs ti be exact. –  andreas-h May 26 '13 at 16:08

Not the answer you're looking for? Browse other questions tagged or ask your own question.