# How to find several rectangles with minimum area to cover the red cells

In Figure 1, (a) is the input mesh, we want to find several rectangles to cover the red cells in (a), at the same time, the sum area of these rectangles should be as small as possible. Figure 1(b) and Figure 1(c) are two ways. Obviously, (c) is a better way due to the smaller sum of area the green rectangles . Besides, the side length of these rectangles should be at least two unit length, for example, the green rectangles in Figure 2 are not allowed. The rectangles can overlap.

How to do this effectively? Is there any algorithm to do this?

I have a simple idea, firstly, use the K-means algorithm to divide these red cells into K clusters, then for each cluster, find a bounding box(rectangle) to cover it. But the sum area of these rectangles may not be small.

• Welcome to CS.SE! 1. Do the rectangles have to be disjoint? (i.e., non-overlapping) 2. What's the context in which you ran into this? Did you design this problem yourself, or get it from another source? Please make sure to credit your sources 3. How efficient do you want/need your algorithm to be? How large will the grids be? 4. Have you tried some kind of dynamic programming?
– D.W.
Apr 16, 2016 at 6:09
• Also posted on Math.SE. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted.
– D.W.
Apr 16, 2016 at 6:11
• Do you want overlap or not? Apr 16, 2016 at 17:52
• The rectangles don't have to be disjoint.
– yang
Apr 17, 2016 at 0:33
• (I don't get any reply - you are expected to give a site's members a fair chance to answer, and "wait" about a week. You can ask moderators to move your question to a different site.) (I design this problem by myself - the images look taken from a text book.) Take a look at boolean logic implementation using Gray code maps. Apr 17, 2016 at 7:24

$\text{minimize } x \cdot area \\ \text{for each red cell } (i,j): \: \sum_{k \in covers(i,j)} x[k] \ge 1 \\ x \in \{0, 1\}$
Where the decision variables x[i] refer to whether or not to use rectangle i, covers(i, j) is the set of rectangles that contain the cell (i, j), area is the vector of the areas of the rectangles, and the set of rectangles used is all 2x2, 2x3, 3x2 and 3x3 rectangles that fit on the grid and contain at least one red cell. You can use a slightly smaller set, for example it is never necessary to use a piece that's bigger than 2x2 that covers only 1 red cell, it could always be replaced by a 2x2 piece and give a better solution. Any rectangles of other legal sizes can be constructed from these pieces so they can be left out.