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 '16 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 '16 at 6:11
• Do you want overlap or not? Apr 16 '16 at 17:52
• The rectangles don't have to be disjoint.
– yang
Apr 17 '16 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 '16 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\}$