Finding a minimal set of rectangles covering a binary matrix

Question

Say I have the following binary matrix:

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

I want to find the set of rectangles parallel to the x and y axis that covers every 1 at least once and covers not a single 0 which has minimal cardinality (the least amount of rectangles). In the example above this would be the rectangles ((0, 3), (6, 5)) and ((3, 0), (5, 8)) (notation is in the form (topleft, bottomright)) - the minimal solution is using two rectangles.

My previous attempt was finding the rectangle with the largest area covering only 1's, adding that rectangle to the set and then marking all those 1's as 0's, until all 1's are gone. While this set would cover every 1 and not a single 0, it won't necessarily have minimal cardinality (this algorithm will fail on the example above).

Answer 1

I think you should replace covered 1's with 2's instead of 0's. This way you can include the 2's when covering 1's and still not cover any 0's.

Here's what I came up with:

#include <stdio.h>
#include <stdlib.h>

struct board {
  int **data;
  int w,h;
};

int  load_board(char *, struct board *);
void print_board(struct board *);

int  max_height_with_fixed_w(struct board *board, int i, int j, int w) {
  int jj = -1, ii;
  if (board->data[j][i] != 0) {
    for (jj = j; jj < board->h && board->data[jj][i] != 0; jj++) { 
      for (ii = i; ii - i < w; ii++) {
        if (board->data[jj][ii] == 0)
          return jj - j;
      }
    }
    printf("maximum height = %d\n", jj);
  }
  return jj - j;
}

void find_largest_rect_from(
    struct board *board, 
    int i, int j, int *ei, int *ej) {
  int max_w = 0, max_h = 0, max_a = 0;
  *ei = *ej = -1;
  for (max_w = 0; max_w < board->w - i && 
      (board->data[j][i + max_w] != 0); 
      max_w++) {
    int max_aa;
    int max_hh = max_height_with_fixed_w(board, i, j, max_w + 1);
    if (max_hh > max_h) {
      max_h  = max_hh; 
    }
    max_aa = max_hh * (max_w + 1);
    printf("  area: %d x %d = %d\n", max_hh, max_w + 1, max_aa);
    if (max_aa > max_a) {
      max_a = max_aa;
      *ei = i + max_w;
      *ej = j + max_hh - 1; 
    }
  }
  printf("max width : %d\n", max_w);
  printf("max height: %d\n", max_h);
  printf("max area  : %d\n", max_a);
}

int main(int arc, char **argv) {
  struct board board;
  int jj, ii, i = 0, j = 0;
  int total_rects = 0;
  if(load_board(argv[1], &board)) return 1;
  print_board(&board);
  for (j = 0; j < board.h; j++) {
    for (i = 0; i < board.w; i++) {
      if (board.data[j][i] == 1) {
        find_largest_rect_from(&board, i, j, &ii, &jj);
        printf("largest from %d, %d ends at %d,%d\n", i, j, ii, jj);
        int marki, markj;
        total_rects++;
        for (markj = j; markj <= jj; markj++) {
          for (marki = i; marki <= ii; marki++) {
            board.data[markj][marki] = 2;
          }
        }
        print_board(&board);
      }
    }
  }
  printf("minimum %d rects are required\n", total_rects);
  return 0;
}

int load_board(char *fname, struct board *board) {
  FILE *file = fopen(fname, "r");
  int j,i;
  if (!file) return 1;
  fscanf(file, "%d %d", &board->w, &board->h);
  board->data = (int**)malloc(sizeof(int*)*board->h);
  for (j = 0; j < board->h; j++) {
    board->data[j] = (int*)malloc(sizeof(int)*board->w);
    for (i = 0; i < board->w; i++) {
      fscanf(file, "%d", &board->data[j][i]);
    }
  }
  return 0;
}

void print_board(struct board *board) {
  int i,j;
  printf("board size: %d, %d\n", board->w, board->h);
  for (j = 0; j < board->h; j++) {
    for (i = 0; i < board->w; i++) {
      printf("%d ", board->data[j][i]);
    } printf("\n");
  }
}

Example input 1:

7 9
0 0 0 1 1 1 0
0 0 0 1 1 1 0
0 0 0 1 1 1 0
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
0 0 0 1 1 1 0
0 0 0 1 1 1 0
0 0 0 1 1 1 0

Example input 2:

7 7
0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0
1 1 1 1 1 1 1
0 1 1 1 1 1 0
0 0 1 1 1 0 0
0 0 0 1 0 0 0

Answer 2

Idea for an algorithm:

• As long as there are 1s in the matrix do:
• For every 1 that doesn't have 1 above it AND doesn't have 1 to its left, do:
• Go greedy: start from this 1 and go in diagonal to the right and down, as long as there are 1s on the way - create a rectangle and change the 1s of the created rectangle into 0s.

Answer 3

I'd go for an algorithm that picks points and expands until it comsumed all possible space, and then picks more, until all points on the grid have been consumed.

For your example, say we're consuming 1s.

I'll pick (0,3), the uppermost of the leftmost 1s. My rectangle would start at a size of 0,0. I'd expand it right and down until it grew to a size of 6,2. At this point, I'd mark those points as occupied.

I'd then pick another point, say (3,0), with a rectangle of size 0,0. I'd grow it down and right until it took up the largest available space, at a size of 2,6.

Consider the following:

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

You can easily determine that for any random starting points, it will always take 4 rectangles.

In order to mark points as "occupied", you should mark them differently than those marked "unconsumable". You can then differentiate between unconsumable (which cannot be expanded into) and "occupied" (which may be expanded into, but do not have to be since they already have been).