Cobertura de grade por retângulos

Temos uma grade . Nós temos uma coleção de retângulos nessa grade, cada retângulo pode ser representado como um -by- binário matriz . Queremos cobrir a grade com esses retângulos.$N_1 \times N_2$$N_1$$N_2$$R$

A versão de decisão deste conjunto cobre o problema NP-complete?

• Entrada: coleção$\mathcal{C}=\{R_1,R_2,\dots,R_L\}$ de retângulos na grade (tamanho da entrada: $N_1N_2L$ ) e $K \in \mathbb{N}^+$
• Saída: Subconjunto $\mathcal{S}\subset\mathcal{C}$ com $|\mathcal{S}|\leq K$ e $\mathcal{S}$ contendo para cada célula pelo menos um retângulo que a cobre.

Descobri que o caso 1D ( $N_2=1$ ) pode ser resolvido em tempo polinomial por meio de programação dinâmica: qualquer cobertura ideal será a união de

• uma cobertura ideal para alguns subproblemas de cobrir as primeiras células $N_1-n_1$ .
• um retângulo 1D, ou seja, um intervalo, cobrindo as $n_1$ células restantes 1 .

Não acho que o DP possa funcionar para o problema 2D: para o problema 1D, você tem um subproblema $N_1$ a ser resolvido, mas para o 2D você tem subproblemas (número de Nordeste) caminhos de rede na grade).$\binom{N_1+N_2}{N_2}$

Acho que o problema pode ser NP, mas não tenho certeza (embora pareça mais difícil que P), e não consegui encontrar uma redução polinomial de um problema NP-completo (3-SAT, Vertex Cover, ...)

Qualquer ajuda ou dica é bem-vinda.

Graças à dica de j_random_hacker, encontrei uma solução para reduzir a cobertura de vértices ao problema de grade:

Nós fazemos um -por- | V | grade de 3 por 3 blocos, ou seja, um 3 | E | -por- 3 | V | grade, com vértices ordenados como colunas { v 1 , … , v N 1 } e arestas ordenadas como linhas { e 1 , … , e N 2 } . Vamos construir retângulos nesta grade (o desenho abaixo ajudará muito a entender os diferentes retângulos usados)$|E|$$|V|$$3|E|$$3|V|$$\{v_1,\dots,v_{N_1}\}$$\{e_1,\dots,e_{N_2}\}$

Para cada vértice, criamos um retângulo do tipo 1, que cobre a coluna central da coluna de blocos correspondente a esse vértice, então temos retângulos do tipo 1.$|V|$

Cada bloco corresponde a um casal único , com e i = ( v a , v b ) para cada bloco, adicionamos um retângulo do tipo 2:$(e_i,v_j)$$e_i=(v_a,v_b)$

• se ou b < j , este é um retângulo de 3 por 3 que cobre todo o bloco.$j<a$$b<j$
• $j=a$$j=b$
• $a<j<b$

$|E||V|$

$(e_i,v_a)$$(e_i,v_b)$

• $(e_i,v_a)$$(e_i,v_b)$

$2|E|$

Agora, para cada aresta, construímos retângulos do tipo 4, entre os blocos finais, temos dois retângulos para a segunda linha:

• Uma que vai da praça central do primeiro bloco à praça central esquerda do segundo bloco.
• Uma que vai da praça central direita do primeiro bloco à praça central do segundo bloco.
• E os mesmos dois retângulos para a terceira linha.

$4|E|$

Então agora, para cobrir a grade:

• $|E|(|V|+2)$$|V|+4|E|$

Para cobrir, para uma determinada aresta, a parte entre os blocos finais da aresta ainda não cobertos (segunda e terceira linhas da linha de blocos), podemos usar:

• o retângulo quatro do tipo 4.
• um retângulo do tipo 1 e dois retângulos do tipo 4.

Observe que, em qualquer caso, precisamos de pelo menos dois retângulos do tipo 4.

$|E|(|V|+4) + k$

• $|E|(|V|+2)$

• $|E|(|V|+4) + k$$|E|(|V|+4) + k$

$|E|(|V|+6) + |V|$$9|V||E|$

$|E|$$3|V|$$|V|+4|E|$$3|E|+k$