Grid covering by rectangles

Question

We have a $N_1 \times N_2$ grid. We have a collection of rectangles on this grid, each rectangle can be represented as a $N_1$-by-$N_2$ binary matrix $R$. We want to cover the grid with those rectangles.

Is the decision version of this set cover problem NP-complete ?

• Input : Collection $\mathcal{C}=\{R_1,R_2,\dots,R_L\}$ of rectangles on the grid (input size: $N_1N_2L$), and $K \in \mathbb{N}^+$
• Output : Subset $\mathcal{S}\subset\mathcal{C}$ with $|\mathcal{S}|\leq K$ and $\mathcal{S}$ containing for each cell at least one rectangle covering it.

I found that the 1D case ($N_2=1$) can be solved in polynomial time by dynamic programming: any optimal cover is going to be the union of

• an optimal cover for some subproblem of covering the first $N_1-n_1$ cells.
• a 1D rectangle, i.e. an interval, covering the remaining $n_1$ cells.

I don't think however DP can work for the 2D problem: for the 1D problem, you have a $N_1$ subproblems to solve, but for 2D you have $\binom{N_1+N_2}{N_2}$ subproblems (number of North-East lattice paths on the grid).

I think the problem might be NP, but I am not sure (though it seems harder than P), and I have not succeed in finding a polynomial reduction from an NP-complete problem (3-SAT, Vertex Cover,...)

Any help or hint is welcome.