Particionar un rectángulo sin dañar los rectángulos internos

$C$ es un rectángulo paralelo al eje.

$C_1,\dots,C_n$ son rectángulos paralelos entre ejes pares tal que , así:$C_1\cup\dots\cup C_n \subsetneq C$

Una partición de C que preserva los rectángulos$C$ es una partición $C = E_1\cup\dots\cup E_N$ , de modo que $N\geq n$ , $E_i$ son rectángulos paralelos en el interior de pares disjuntos, y para cada $i=1,\dots,n$ : $C_i \subseteq E_i$ , es decir, cada rectángulo existente está contenido en un nuevo rectángulo único, como este:

¿Qué es un algoritmo para encontrar una partición de preservación de rectángulo con una pequeña ?$N$

En particular, ¿hay un algoritmo para encontrar una partición de preservación de rectángulo con partes?$N=O(n)$

NUEVA RESPUESTA: el siguiente algoritmo simple es asintóticamente óptimo:

Estire cada uno de los rectángulos arbitrariamente, en la mayor medida posible de modo que los rectángulos permanezcan separados por pares.$C_i$

El número de agujeros es como máximo . Esto es asintóticamente óptimo, ya que hay configuraciones en las que el número de agujeros es al menos .$k-2$$k-O(\sqrt k)$

Las pruebas están en este documento .

ANTIGUA RESPUESTA:

El siguiente algoritmo, aunque no es óptimo, es aparentemente suficiente para encontrar una partición de preservación de rectángulo con partes .$N=O(n)$

El algoritmo trabaja con un polígono rectilíneo , que se inicializa en el rectángulo .$P$$C$

Fase 1: Elija un rectángulo que esté adyacente a un límite occidental de (es decir, no hay otro rectángulo entre el lado occidental de y un límite occidental de ). Lugar dentro de y estirar hasta que toque el límite occidental de . Deje que (para ) sea la versión extendida de . Deje . Repita la fase 1 veces hasta que todas$C_i$$P$$C_j$$C_i$$P$$C_i$$P$$P$$E_i$$i=1,\dots,n$$C_i$$P=P\setminus E_i$$n$$n$Los rectángulos originales se colocan y se estiran. En la imagen a continuación, un posible orden de colocación de los rectángulos es :$C_1,C_2,C_4,C_3$

Ahora, es un polígono rectilíneo (posiblemente desconectado), como este:$P$

Afirmo que el número de vértices cóncavos en es como máximo . Esto se debe a que, cada vez que se elimina un rectángulo estirado de , hay 3 posibilidades:$P$$2n$$P$

• Se agregan 2 nuevos vértices cóncavos (como al colocar );$C_1,C_4$
• Se agregan 3 vértices cóncavos nuevos y se elimina 1 (como con );$C_3$
• Se agregan 4 vértices cóncavos nuevos y se eliminan 2 (como con ).$C_2$

Fase 2: Partición en rectángulos paralelos al eje usando un algoritmo existente (ver Keil 2000, páginas 10-13 y Eppstein 2009, páginas 3-5 para una revisión).$P$

Keil cita un teorema que dice que el número de rectángulos en una partición mínima está limitado por 1 + el número de vértices cóncavos. Por lo tanto, en nuestro caso, el número es como máximo , y el número total de rectángulos en la partición es .$2n+1$$N\leq 3n+1$

Este algoritmo no es óptimo. Por ejemplo, en el ejemplo anterior da mientras que la solución óptima tiene . Entonces quedan dos preguntas:$N=13$$N=5$

A. ¿Es correcto este algoritmo?

B. ¿Existe un algoritmo de tiempo polinómico para encontrar el óptimo , o al menos una mejor aproximación?$N$