2

I've got a 2D-binary matrix of arbitrary size. I want to find a set of rectangles in this matrix, showing a maximum area. The constraints are:

  • Rectangles may only cover "0"-fields in the matrix and no "1"-fields.
  • Each rectangle has to have a given distance from the next rectangle.

So let me illustrate this a bit further by this matrix:

1 0 0 1
0 0 0 0
0 0 1 0
0 0 0 0
0 1 0 0

Let the minimal distance between two rectangles be 1. Consequently, the optimal solution would be by choosing the rectangles with corners (1,0)-(3,1) and (1,3)-(4,3). These rectangles are min. 1 field apart from each other and they do not lie on "1"-fields. Additionally, this solution got the maximum area (6+4=10).

If the minimal distance would be 2, the optimum would be (1,0)-(4,0) and (1,3)-(4,3) with area 4+4=8.

Till now, I achieved to find out rectangles analogous to this post: Find largest rectangle containing only zeros in an N×N binary matrix

I saved all these rectangles in a list:

list<rectangle> rectangles;

with

struct rectangle {
    int i,j; // bottom left corner of rectangle
    int width,length; // width=size in neg. i direction, length=size in pos. j direction
};

Till now, I only thought about brute-force-methods but of course, I am not happy with this.

I hope you can give me some hints and tips of how to find the corresponding rectangles in my list and I hope my problem is clear to you.

Community
  • 1
  • 1
Kapa11
  • 311
  • 2
  • 18
  • It is restricted for a rectangle to be not a square? and can it have area=1? – Rama Dec 06 '16 at 13:13
  • It does not have to be a square but in my code I got restrictions with respect to length and width of a rectangle. For my purposes the matrix is at least 50x50 large and a rectangle got a minimal size of 3x3. – Kapa11 Dec 06 '16 at 13:22
  • Is integer programming an option? – David Eisenstat Dec 06 '16 at 16:07
  • Oh, actually I have to confess I got not much knowledge about integer programming. Could you maybe very briefly explain what you mean with this in the given context? – Kapa11 Dec 07 '16 at 07:23

1 Answers1

2

The following counterexample shows that even a brute-force checking of all combinations of maximal-area rectangles can fail to find the optimum:

110
000
110

In the above example, there are 2 maximal-area rectangles, each of area 3, one vertical and one horizontal. You can't pick both, so if you are restricted to choosing a subset of these rectangles, the best you can do is to pick (either) one for a total area of 3. But if you instead picked the vertical area-3 rectangle, and then also took the non-maximal 1x2 rectangle consisting of just the leftmost two 0s, you could get a better total area of 5. (That's for a minimum separation distance of 0; if the minimum separation distance is 1, as in your own example, then you could instead pick just the leftmost 0 as a 1x1 rectangle for a total area of 4, which is still better than 3.)

For the special case when the separation distance is 0, there's a trivial algorithm: you can simply put a 1x1 rectangle on every single 0 in the matrix. When the separation distance is strictly greater than 0, I don't yet see a fast algorithm, though I'm less sure that the problem is NP-hard now than I was a few minutes ago...

j_random_hacker
  • 50,331
  • 10
  • 105
  • 169