Número mínimo de rectángulos necesarios para cubrir un conjunto de cuadrados en un $\text{N} \times \text{N}$ cuadrícula

Question

Existe un $\text{N} \times \text{N}$ cuadrícula de cuadrados. Algún subconjunto arbitrario de esos cuadrados debe estar cubierto por algún número de rectángulos (un cuadrado dado debe estar cubierto enteramente por un rectángulo, los rectángulos sólo pueden cubrir estas áreas, nada más). ¿Cómo puedo hallar el conjunto de rectángulos que cubre todo un conjunto dado de cuadrados con el menor número posible de rectángulos?

¿Cuál es el número máximo de rectángulos necesarios para rellenar cualquier subconjunto de un $\text{N} \times \text{N}$ cuadrado?

Answer 1

Este es el problema de la compresión rectilínea de imágenes que se sabe que es NP-difícil (véase el libro de texto Computer and Intractability, a guide to the theory of NP-completeness de Garey y Johnson, p. 232, SR25). Así que nadie te dará una solución en tiempo polinómico si $\mathrm{P} \ne \mathrm{NP}$ . Puede aplicar métodos para resolver problemas NP-duros, por ejemplo, brunch and bounds.

EDIT: La nota anterior se refería a la versión de portada del problema. Para la versión de partición hay algoritmos de tiempo polinómico. Usted puede comenzar a partir de Algoritmos eficientes para problemas de búsqueda de grafos geométricos de Hiroshi Imai y Takao Asano, subsección 7.1. Por lo que veo en su caso, establece lo siguiente $O(N^{5/2})$ -para una única región de cuadrados conectada y, por lo tanto $O(N^{7/2})$ -tiempo en total.

Parece que pintar la cuadrícula como un tablero de ajedrez da el máximo número $\left\lceil\frac{N^2}2\right\rceil$ de rectángulos necesarios, sin embargo ahora no puedo dar una prueba rigurosa.