# covering an NxN grid using overlapping vs. non-overlapping windows residing k points in each

Let the problem, $P_{overlapping}$, be the following. We have an $N_1 \times N_2$ grid. Each cell of the grid can have the value either 0 or 1. Assume that we have $a \times b$ overlapping windows as the subset of the $N_1 \times N_2$ grid where $a < N_1$ and $b < N_2$, and we want to have at least $k$ of the cells in each window have the value 1. We are interested in minimizing the number of cells having the value 1 when $N_1 \times N_2$ grid is covered by $a \times b$ overlapping windows having $k$ cells with the value 1 in each.

And, let the problem, $P_{non-overlapping}$, be the following. We have an $N_1 \times N_2$ grid, and each cell of the grid can have the value either 0 or 1 similar to the problem, $P_{overlapping}$. But this time, assume that we have $a \times b$ non-overlapping windows as the subset of the $N_1 \times N_2$ grid where $a < N_1$ and $b < N_2$, and we want to have at least $k$ of the cells in each window have the value 1. We are interested in minimizing the number of cells having the value 1 when $N_1 \times N_2$ grid is covered by $a \times b$ non-overlapping windows having $k$ cells with the value 1 in each.

For an $N \times N$ grid, $\left \lfloor \frac{N}{a} \right \rfloor \times \left \lfloor \frac{N}{b} \right \rfloor \times k$ is the lower bound for $P_{non-overlapping}$. In order to find optimal solutions for the problem $P_{overlapping}$, I used the following Integer Linear Programming formulation:

\begin{align} \label{eqnew:01} \mbox{Minimize: } &\sum_{i=1}^{N_1}\sum_{j=1}^{N_2} x_{ij}} &;& x_{ij} \in \{0,1\} \notag \\ \mbox{Subject To: } & \sum_{i=m}^{m+a-1} \ \sum_{j=n}^{n+b-1} x_{ij} \ge k} &;& \forall{m}, \ 1 \le m \le N_1-a+1 \notag \\ & &,& \forall{n}, \ 1 \le n \le N_2-b+1 \end{align}

And using GLPK linear programming solver, and solving the problem for some $N \times N$ grids with $a \times b (12 \times 9)$ overlapping windows for $k=2$, I got some results for optimum solutions for $P_{overlapping}$. Interestingly, when I used the lower bound for the problem $P_{non-overlapping}$, $N \times N$ grid, $\left \lfloor \frac{N}{12} \right \rfloor \times \left \lfloor \frac{N}{9} \right \rfloor \times 2$ for $k=2$; solutions for both problems are the same as seen in the following graph

comparison of the problems

And, finally, my question is the following. Why are these two different problems have the same solutions for $k=2$? How about for $k$ values other than 2? Is this reasonable theoretically?

Many thanks for your time, fellas.

Baris

• In other words, you want to assign values to entries in the matrix to satisfy the constraints on the subrectangles ? that was not clear in your question. And notice that your "lower bound" which comes from placing 1s in an even pattern is also a valid solution for the overlapping case if I understand the problem correctly. – Suresh Venkat Dec 2 '11 at 6:54
• Yes, we are assigning values to entries in the matrix to satisfy the constraints on the subrectangles. Why is the solution for the non-overlapping subrectangles case also – Baris Dec 2 '11 at 19:00
• Yes, we are assigning values to entries in the matrix to satisfy the constraints on the subrectangles. Why is the solution for the non-overlapping subrectangles case also valid for the overlapping subrectangles case? Is this provable? Shouldn't the overlapping case have more number of entries assigned to the matrix compared to the non-overlapping case? ("I'm using floor for the "lower bound" computation") – Baris Dec 2 '11 at 19:08