Partición de guillotina

Proceso de partición de un polígono rectilíneo

Un corte de guillotina: una hoja optimizada de rectángulos más pequeños que se puede dividir intacta a través de la serie correcta de cortes bisectores de extremo a extremo.

Un corte sin guillotina: estos rectángulos no se pueden separar haciendo cortes biseccionales simples a lo largo del plano.

La partición con guillotina es el proceso de dividir un polígono rectilíneo , que posiblemente contenga algunos 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 bisecta desde un borde de un polígono existente hasta el borde opuesto, de manera 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 una partición de corte o un plano de planta de corte . ^[1] Las particiones de guillotina también son la estructura subyacente de las particiones espaciales binarias . Existen 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. Estas son variantes de los 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 ese problema, la hoja original es un rectángulo simple sin agujeros. El desafío surge del hecho de que las dimensiones de los pequeños rectángulos se fijan de antemano. Los objetivos de optimización suelen ser maximizar el área de los rectángulos producidos o su valor, o minimizar el desperdicio o la cantidad de hojas necesarias.

Cálculo de una partición de guillotina con la longitud de arista más pequeña

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

Este problema se puede resolver a tiempo incluso si el polígono en 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 posibles elecciones para el siguiente corte de guillotina y hay en total subproblemas. ${\displaystyle O(n^{5})}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{4})}$

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-duro.

Estos resultados se pueden extender a una caja de dimensión d : se puede encontrar una partición de guillotina con una longitud de arista mínima en el tiempo , y el volumen total ( d -1) en la partición de guillotina óptima es en la mayoría de los casos el de una partición de caja d óptima . ^[4] ${\displaystyle O(dn^{2d+1})}$ ${\displaystyle 2d-4+4/d}$

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.

Número de particiones de guillotina

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, hay infinitas formas de hacer esto, 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 atribuido a Knuth . El número exacto es el número de Schröder . ^[7] ${\displaystyle O\left({\frac {n!2^{5n-3}}{n^{3/2}}}\right)}$
• En dimensiones d , Ackerman, Barequet, Pinter y Romik ^[8] dan una fórmula de suma exacta y prueban que está en . Cuando d = 2 este límite se convierte en . ${\displaystyle \Theta \left({\frac {(2d-1+2{\sqrt {d(d-1)}})^{n}}{n^{3/2}}}\right)}$ ${\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 las particiones de guillotina.

Particiones de guillotina para colorear

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

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

Véase también

• Partición del espacio binario

Referencias

1. Lengauer, Thomas (1990), "Partición de circuitos", Algoritmos combinatorios para el diseño de circuitos integrados , Wiesbaden: Vieweg+Teubner Verlag, págs. 251–301, doi :10.1007/978-3-322-92106-2_6, ISBN 978-3-322-92108-6, consultado el 16 de enero de 2021
2. Du, Ding-Zhu; Ko, Ker-I.; Hu, Xiaodong (2012). Diseño y análisis de algoritmos de aproximación. Optimización de Springer y sus aplicaciones. Nueva York: Springer-Verlag. págs. 165-209, capítulo 5 "corte de guillotina". ISBN 978-1-4614-1700-2.
3. Gonzalez, Teofilo; Zheng, Si-Qing (1989-06-01). "Límites mejorados para particiones rectangulares y de guillotina". Journal of Symbolic Computation . 7 (6): 591–610. doi : 10.1016/S0747-7171(89)80042-2 . ISSN  0747-7171.
4. Gonzalez, Teofilo F.; Razzazi, Mohammadreza; Shing, Man-Tak; Zheng, Si-Qing (1994-05-01). "Sobre particiones de guillotina óptimas que se aproximan a particiones de d-box óptimas". Geometría Computacional . 4 (1): 1–11. doi : 10.1016/0925-7721(94)90013-2 . ​​ISSN  0925-7721.
5. Arora, S. (octubre de 1996). "Esquemas de aproximación temporal polinómica para TSP euclidiano y otros problemas geométricos". Actas de la 37.ª Conferencia sobre Fundamentos de la Ciencia de la Computación . págs. 2–11. doi :10.1109/SFCS.1996.548458. ISBN. 0-8186-7594-2.S2CID 1499391  .
6. Mitchell, Joseph SB (1 de enero de 1999). "Las subdivisiones de guillotina aproximan subdivisiones poligonales: un esquema simple de aproximación en tiempo polinomial para problemas geométricos TSP, k-MST y relacionados". Revista SIAM de informática . 28 (4): 1298–1309. doi :10.1137/S0097539796309764. ISSN  0097-5397.
7. Yao, Bo; Chen, Hongyu; Cheng, Chung-Kuan; Graham, Ronald (1 de enero de 2003). "Representaciones de planos de planta: complejidad y conexiones". ACM Transactions on Design Automation of Electronic Systems . 8 (1): 55–80. doi :10.1145/606603.606607. ISSN  1084-4309. S2CID  1645358.
8. Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y.; Romik, Dan (31 de mayo de 2006). "El número de particiones de guillotina en dimensiones d". Information Processing Letters . 98 (4): 162–167. doi :10.1016/j.ipl.2006.01.011. ISSN  0020-0190.
9. Asinowski, Andrei; Barequet, Gill; Mansour, Toufik; Pinter, Ron Y. (28 de septiembre de 2014). "Equivalencia de corte de particiones de guillotina de dimensión d". Matemáticas discretas . 331 : 165–174. doi : 10.1016/j.disc.2014.05.014 . ISSN  0012-365X.
10. Dinitz, Yefim; Katz, Matthew J.; Krakovski, Roi (1 de diciembre de 2009). "Protección de particiones rectangulares". Revista internacional de geometría computacional y aplicaciones . 19 (6): 579–594. doi :10.1142/S0218195909003131. ISSN  0218-1959.
11. Horev, Elad; Katz, Matthew J.; Krakovski, Roi; Löffler, Maarten (15 de junio de 2009). "Cuatro colores policromáticos de subdivisiones de guillotina". Information Processing Letters . 109 (13): 690–694. doi :10.1016/j.ipl.2009.03.006. ISSN  0020-0190.
12. Keszegh, Balázs (2008). Hu, Xiaodong; Wang, Jie (eds.). "Coloraciones policromáticas de particiones de guillotina n-dimensionales". Computing and Combinatorics . Apuntes de clase en informática. 5092 . Berlín, Heidelberg: Springer: 110–118. doi :10.1007/978-3-540-69733-6_12. ISBN 978-3-540-69733-6.
13. Dimitrov, Darko; Horev, Elad; Krakovski, Roi (6 de mayo de 2009). "Coloraciones policromáticas de particiones rectangulares". Matemáticas discretas . 309 (9): 2957–2960. doi : 10.1016/j.disc.2008.07.035 . ISSN  0012-365X.