6
$\begingroup$

enter image description here

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.

enter image description here

$\endgroup$
8
  • 1
    $\begingroup$ 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? $\endgroup$
    – D.W.
    Apr 16, 2016 at 6:09
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Apr 16, 2016 at 6:11
  • 1
    $\begingroup$ Do you want overlap or not? $\endgroup$
    – harold
    Apr 16, 2016 at 17:52
  • 1
    $\begingroup$ The rectangles don't have to be disjoint. $\endgroup$
    – yang
    Apr 17, 2016 at 0:33
  • 1
    $\begingroup$ (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. $\endgroup$
    – greybeard
    Apr 17, 2016 at 7:24

1 Answer 1

2
$\begingroup$

The way I created the pictures in my comment is by Integer Linear Programming, specifically the following model:

$\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.

Actually even fewer rectangles can be used. For example, a rectangle that can be replaced by a smaller rectangle without uncovering any red cells is redundant. There is also the case where a 3x3 can be replaced by 2 2x2 rectangles, that potentially overlap, such that they together cover (at least) the same red cells, making the 3x3 redundant.

Experiment shows that presolving removes almost all columns (for relatively sparse problems), suggesting that it should be easy to a-priori not-generate many of them. I have not looked into that too deeply yet.

Despite ILP being NP-hard, large instances such as this or even this were solved in a couple of seconds. Maybe there is also an inherently efficient way though, I'm not sure.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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