llenando un plano ocluido con el menor número de rectángulos

Question

Tengo un problema específico que voy a tratar de describir lo más claramente posible.

Tengo definida una región rectangular en un plano cartesiano, y dentro de esa región hay otros rectangular sub-regiones que se describen en términos de sus 4 vértices, es decir, {(x1, y1), (x1, y2), (x2, y1), (x2, y2)}, por lo que estas regiones de la forma "oclusiones' en el avión. Estas regiones no se superponen, sino que se pueden formar más complejo de los polígonos al diferente tamaño de los rectángulos adyacentes a cada uno de los otros aparecen unidas.

he aquí una ilustración:

Estoy interesado en el espacio entre estas formas, y cómo definir el espacio de la misma manera que las oclusiones se definen, que es como un conjunto de rectángulos. En particular, quiero la definición optimizados de manera que el espacio se describe utilizando el menor número posible de rectángulos. Por ejemplo, una representación incompleta podría tener este aspecto:

Puede alguien sugerir una manera de seguir adelante con esto? ¿Cómo puedo tener el original conjunto de vértices (describiendo los rectángulos negros) generar el 'complementarias' conjunto de vértices (rojo rectángulos) de tal manera que el número de rectángulos rojo es mínima?

Sospecho que es una variación de un "embalaje problema', pero tengo la sensación de que podría ser bastante simple...

Answer 1

Este problema ha sido estudiado en la década de 1980. Usted puede encontrar que es llamado el problema de encontrar un mínimo rectángulo partición de un polígono ortogonal con agujeros. En la literatura antigua, a veces "ortogonal" es reemplazado por "rectilíneo." Si ajusta su rectángulos negros con el mínimo de la caja de contorno, luego convertida a un polígono ortogonal con agujeros.

Creo que el primer resultado fue de Lipsky en 1979, pero no estoy encontrando que de papel. Aquí es un poco más tarde de papel:

"Creación de particiones rectilíneo cifras en rectángulos." 1988. (ACM enlace)

A pesar de que muchos de los problemas superficialmente análoga a este son NP-hard, este rectángulo-partición problema puede ser resuelto en $O(n^{5/2})$ tiempo para un polígono de $n$ vértices en total. Los algoritmos depende de la búsqueda de un máximo conjunto independiente de la intersección de la gráfica de ciertos acordes en el polígono.

---

(Añadido 8Jul14): En respuesta a Rahul consultas, he de decir en los comentarios que para un simple polígono ortogonal (sin agujeros), el mínimo rectángulo la partición puede ser encontrado en $O(n \log \log n)$ del tiempo.