Partición de un polígono
En geometría, una partición de un polígono es un conjunto de unidades primitivas (por ejemplo, cuadrados), que no se superponen y cuya unión es igual a un polígono dado.
El término descomposición de polígonos se utiliza a menudo como un término general que incluye tanto el recubrimiento de un polígono como su partición.
Para un polígono con agujeros, existe un límite inferior de
En este caso, la forma del componente más importante a considerar es el rectángulo.
Fue estudiado por primera vez por Lingas, Pinter, Rivest y Shamir en 1982.
Si el polígono sin formato está libre de agujeros, entonces se puede encontrar una partición óptima en el tiempo
[4] El algoritmo utiliza programación dinámica y se basa en el siguiente hecho: si el polígono no tiene agujeros, entonces tiene una partición de longitud mínima en la que cada segmento de línea máximo contiene un vértice del límite.
Esto se puede demostrar mediante la reducción Planar SAT.
[4][6] Para el caso en el que todos los agujeros son puntos aislados, se han desarrollado varias aproximaciones de factor constante: En esta configuración, el polígono grande ya contiene algunos rectángulos separados por pares.
El objetivo es encontrar una partición del polígono en rectángulos de modo que cada rectángulo original esté contenido en una de las piezas y, sujeto a esto, el número de espacios en blanco (piezas que no contienen un rectángulo original) sea tan pequeño como sea posible.
[13] Si el número de trapecios no tiene por qué ser mínimo, se puede encontrar una solución trapezoidal en el tiempo
[14] Si el polígono contiene agujeros, el problema es NP-completo, pero se puede encontrar una aproximación de 3 en el tiempo
Permitir puntos de Steiner puede permitir divisiones más pequeñas, pero entonces es mucho más difícil garantizar que las divisiones encontradas por un algoritmo tengan un tamaño mínimo.
Aquí el objetivo es minimizar la longitud total de los bordes.
Este problema se puede resolver en tiempo polinómico en n y m.[17][18] Al dividir un polígono general en polígonos convexos se han estudiado varios objetivos.
Existen algoritmos exactos y aproximados para este problema.
[19] El polígono original ya contiene algunas figuras convexas disjuntas por pares, y el objetivo es dividirlo en polígonos convexos de manera que cada figura original esté contenida en una de las piezas, y sujeto a esto, el número de espacios en blanco (piezas que no contienen la figura original) sea lo más pequeño posible.
[21] Una generalización de este problema es cuando las medidas de área y perímetro se reemplazan con una medida en el cuerpo y en el límite del polígono, respectivamente.
[22] Existe una generalización adicional para manejar cualquier número de medidas.
Consúltese el trabajo de J. Mark Keil[1] para ver desarrollos al respecto.
