# How to slice an area in rectangles optimally? [duplicate]

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?

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.

-

## marked as duplicate by Rahul, Meta, William, amWhy, Adam HughesSep 3 '14 at 22:28

This question was marked as an exact duplicate of an existing question.

That is a cool picture. – Stefan Smith May 25 '13 at 20:13
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

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).

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