partición de guillotina

La partición con guillotina es el proceso de dividir un polígono rectilíneo , que posiblemente contenga agujeros, en rectángulos, utilizando únicamente cortes de guillotina. Un corte de guillotina (también llamado corte de borde a borde ) es una línea recta que biseca un polígono existente desde un borde hasta el borde opuesto, de forma similar a una guillotina de papel .

La partición de guillotina es particularmente común en el diseño de planos de planta en microelectrónica . Un término alternativo para una partición de guillotina en este contexto es partición de corte o plano de planta de corte . ^{[ 1 ]} Las particiones de guillotina también son la estructura subyacente de las particiones de espacio binario . Hay varios problemas de optimización relacionados con la partición de guillotina, como minimizar el número de rectángulos o la longitud total de los cortes. Estos son variantes de problemas de partición de polígonos , donde los cortes están restringidos a ser cortes de guillotina.

Un problema relacionado, pero diferente, es el corte con guillotina . En este caso, la lámina original es un rectángulo liso sin perforaciones. La dificultad radica en que las dimensiones de los pequeños rectángulos están predefinidas. Los objetivos de optimización suelen ser maximizar el área o el valor de los rectángulos resultantes, o minimizar el desperdicio o la cantidad de láminas necesarias.

En el problema de partición rectangular de longitud de arista mínima , el objetivo es dividir el polígono rectilíneo original en rectángulos, de manera que la longitud total de la arista sea mínima. ^{[ 2 ] : 166–167}

Este problema se puede resolver a tiempo.${\displaystyle O(n^{5})}$incluso si el polígono bruto tiene agujeros. El algoritmo utiliza programación dinámica basada en la siguiente observación: existe una partición rectangular de guillotina de longitud mínima en la que cada segmento de línea máximo contiene un vértice del límite . Por lo tanto, en cada iteración, hay${\displaystyle O(n)}$posibles opciones para el próximo corte de guillotina, y hay todas${\displaystyle O(n^{4})}$subproblemas.

En el caso especial en el que todos los agujeros son degenerados (puntos únicos), la partición rectangular de guillotina de longitud mínima es como máximo 2 veces la partición rectangular de longitud mínima. ^{[ 2 ] : 167–170} Mediante un análisis más cuidadoso, se puede demostrar que el factor de aproximación es de hecho como máximo 1,75. No se sabe si 1,75 es ajustado, pero hay un caso en el que el factor de aproximación es 1,5. ^{[ 3 ]} Por lo tanto, la partición de guillotina proporciona una aproximación de factor constante al problema general, que es NP-difícil.

Estos resultados pueden extenderse a una caja d -dimensional: se puede encontrar una partición de guillotina con longitud de arista mínima en tiempo${\displaystyle O(dn^{2d+1})}$y el volumen total ( d -1) en la partición de guillotina óptima es como máximo${\displaystyle 2d-4+4/d}$veces la de una partición d -box óptima. ^{[ 4 ]}

Arora ^{[ 5 ]} y Mitchell ^{[ 6 ]} utilizaron la técnica de partición de guillotina para desarrollar esquemas de aproximación de tiempo polinomial para varios problemas de optimización geométrica.

Además de los problemas computacionales, las particiones de guillotina también se estudiaron desde una perspectiva combinatoria. Supongamos que un rectángulo dado debe dividirse en rectángulos más pequeños utilizando únicamente cortes de guillotina. Obviamente, existen infinitas maneras de hacerlo, ya que incluso un solo corte puede tomar infinitos valores. Sin embargo, el número de particiones de guillotina estructuralmente diferentes es limitado.

• En dos dimensiones, existe un límite superior en${\displaystyle O\left({\frac {n!2^{5n-3}}{n^{3/2}}}\right)}$Atribuido a Knuth . El número exacto es el número de Schröder . ^{[ 7 ]}
• En d dimensiones, Ackerman, Barequet, Pinter y Romik ^{[ 8 ]} dan una fórmula de suma exacta y demuestran que está en${\displaystyle \Theta \left({\frac {(2d-1+2{\sqrt {d(d-1)}})^{n}}{n^{3/2}}}\right)}$Cuando d = 2, este límite se convierte en...${\displaystyle \Theta \left({\frac {(3+2{\sqrt {2}})^{n}}{n^{3/2}}}\right)}$.
• Asinowski, Barequet, Mansour y Pinter ^{[ 9 ]} también estudian el número de clases de equivalencia de corte de particiones de guillotina.

Una coloración policromática de un grafo planar es una coloración de sus vértices tal que, en cada cara del grafo, cada color aparece al menos una vez. Varios investigadores han intentado encontrar el mayor valor de k tal que siempre exista una k -coloración policromática. Un caso especial importante se da cuando el grafo representa una partición de un rectángulo en rectángulos.

• Dinitz, Katz y Krakovski ^{[ 10 ]} demostraron que siempre existe una coloración policromática de 3 colores.
• Aigner-Horev, Katz, Krakovski y Loffler ^{[ 11 ]} demostraron que, en el subcaso especial en el que el grafo representa una partición de guillotina , siempre existe una 4-coloración policromática fuerte.
• Keszegh ^{[ 12 ]} extendió este resultado a particiones de guillotina d -dimensionales y proporcionó un algoritmo de coloración eficiente.
• Dimitrov, Aigner-Horev y Krakovski ^{[ 13 ]} finalmente demostraron que siempre existe una fuerte 4-coloración policromática.

• Particionamiento binario del espacio