Partición de guillotina
La partición de guillotina es el proceso de dividir un polígono rectilíneo , que posiblemente contenga algunos agujeros, en rectángulos, usando solo cortes de guillotina. Un corte de guillotina (también llamado corte de borde a borde ) es una línea bisectriz recta que va desde un borde de un polígono existente hasta el borde opuesto, 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 piso de corte . [1] Las particiones de guillotina también son la estructura subyacente de las particiones de espacio binario . Existen varios problemas de optimización relacionados con la partición de guillotina, tales 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 proviene 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 el número de hojas requeridas.
En el problema de partición rectangular de longitud mínima de arista , el objetivo es dividir el polígono rectilíneo original en rectángulos, de modo que la longitud total de la arista 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 de la frontera . Por lo tanto, en cada iteración, hay opciones posibles para el siguiente corte de guillotina y hay subproblemas en conjunto.
En el caso especial en el que todos los agujeros son degenerados (puntos únicos), el tabique rectangular de guillotina de longitud mínima es como máximo 2 veces el tabique 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 el 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.
