Partición de un polígono

Algunos casos especiales de partición de polígonos: una colección de polígonos divisibles en formas congruentes a sí mismas (denominadas repiteselas)

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. Un problema de partición poligonal consiste en encontrar una disección que sea mínima en algún sentido, como por ejemplo, una partición con el menor número de unidades o con unidades de longitud lateral total más pequeña.

La partición de polígonos es una clase importante de problemas en geometría computacional. Hay muchos problemas diferentes de partición de polígonos, según el tipo de polígono objeto de partición y de los tipos de unidades permitidas en la misma.

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.[1]​

Aplicaciones

La descomposición de polígonos se aplica en varias áreas:[1]​

• Las técnicas de reconocimiento de patrones extraen información de un objeto para poder describirlo, identificarlo o clasificarlo. Una estrategia establecida para reconocer un objeto poligonal general es descomponerlo en componentes más simples, luego identificar los componentes y sus interrelaciones y utilizar esta información para determinar la forma del objeto.
• En el procesamiento de datos mediante integración a muy gran escala, los diseños se representan como polígonos, y un método de preparación para la litografía por haz de electrones es descomponer estas regiones poligonales en figuras fundamentales. La descomposición de polígonos también se utiliza en el proceso de dividir la región de enrutamiento en canales.
• En geometría computacional, los algoritmos para problemas de polígonos generales suelen ser más complejos que los de tipos restringidos de polígonos, como los convexos o los de forma de estrella. El problema de un punto en un polígono es un ejemplo. Una estrategia para resolver algunos de estos tipos de problemas en polígonos generales es descomponer el polígono en componentes simples, resolver el problema en cada componente usando un algoritmo especializado y luego combinar las soluciones parciales.
• Otras aplicaciones incluyen la compresión de datos, las bases de datos, el procesamiento digital de imágenes y la computación gráfica.

Dividir un polígono en triángulos

El problema de partición de polígonos mejor estudiado es la partición en el menor número de triángulos, también llamado triangulación. Para un polígono sin agujeros y con ${\displaystyle n}$ vértices, se puede calcular una triangulación en el tiempo ${\displaystyle \Theta (n)}$. Para un polígono con agujeros, existe un límite inferior de ${\displaystyle \Omega (n\log n)}$.

Un problema relacionado es la partición en triángulos con una longitud total de aristas mínima, también llamada triangulación de peso mínimo.

Dividir un polígono en pseudotriángulos

Se han estudiado las mismas dos variantes del problema para el caso en el que las piezas deberían ser pseudotriángulos: polígonos que, al igual que los triángulos, tienen exactamente tres vértices convexos. Las variantes son: dividir en un número más pequeño de pseudotriángulos y dividir en pseudotriángulos con una longitud total mínima de aristas.

Dividir un polígono rectilíneo en rectángulos

Una subfamilia especial de problemas de partición de polígonos surge cuando el polígono grande es un polígono rectilineal (también llamado: polígono ortogonal). En este caso, la forma del componente más importante a considerar es el rectángulo.[1]​

Las particiones rectangulares tienen muchas aplicaciones. En el diseño de integración a muy gran escala, es necesario descomponer las máscaras en las formas más simples disponibles en los generadores de patrones litográficos, y también surgen problemas similares de descomposición de máscaras en el diseño de micromatrices de ácido desoxirribonucleico. Las particiones rectangulares pueden simplificar las operaciones de convolución en el procesamiento digital de imágenes y pueden usarse para comprimir gráficos rasterizados. Se han aplicado problemas de descomposición de matrices estrechamente relacionados con la planificación de los tratamientos de radioterapia, y también se han utilizado particiones rectangulares para diseñar secuencias de autoensamblaje robótico.[2]​

Minimizar el número de componentes

El problema de minimizar el número de rectángulos componentes es polinómico: se conocen varios algoritmos en tiempo polinómico. Consúltese[1]​: 10–13  y[2]​: 3–5  para ver desarrollos al respecto.

El problema de dividir un polígono rectilíneo en el menor número de "cuadrados" (a diferencia de los rectángulos arbitrarios) es NP-difícil.[3]​

Minimizar la longitud total de las aristas

En algunas aplicaciones, es más importante minimizar la longitud total de cortes necesarios (por ejemplo, para minimizar el costo de realizar la partición o reducir la cantidad de polvo generado). Este problema se denomina partición rectangular de longitud mínima de borde. Fue estudiado por primera vez por Lingas, Pinter, Rivest y Shamir en 1982.[4]​[5]​ La complejidad en tiempo de ejecución de este problema depende crucialmente de si se permite que el polígono en bruto tenga agujeros o no.

Si el polígono sin formato está libre de agujeros, entonces se puede encontrar una partición óptima en el tiempo ${\displaystyle O(n^{4})}$, donde n es el número de vértices del polígono. En el caso especial de un polígono de histograma, la complejidad mejora a ${\displaystyle O(n^{3})}$.[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. La razón es que, en cualquier partición de longitud mínima, cada segmento de línea máximo puede ser empujado hasta que llegue a uno de los vértices del límite, sin cambiar la longitud total. Por lo tanto, solo hay ${\displaystyle O(n^{2})}$ candidatos para un segmento de línea en una partición óptima, y se pueden verificar de manera eficiente mediante programación dinámica.[5]​: 166–167 

Si el polígono en bruto puede tener agujeros, incluso si son agujeros degenerados (es decir, puntos aislados), el problema es NP-difícil. 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:

• Una aproximación de (3+sqrt(3)) en el tiempo ${\displaystyle O(n^{2})}$.[6]​
• Una aproximación de (3+sqrt(3)) en el tiempo ${\displaystyle O(n\log {n})}$.[7]​
• Una aproximación de 4 en el tiempo ${\displaystyle O(n\log {n})}$ (más generalmente, en d dimensiones, es una aproximación de ${\displaystyle 2d}$ en el tiempo ${\displaystyle O(dn\log {n})}$).[8]​
• Una aproximación de 3 en el tiempo ${\displaystyle O(n^{4})}$.
• Una aproximación de 1,75 en el tiempo ${\displaystyle O(n^{5})}$ (más generalmente, en d dimensiones, es una aproximación ${\displaystyle 2d-4+4/d}$ en el tiempo ${\displaystyle O(dn^{2d+1})}$).[9]​ Esta última aproximación utiliza una variante restringida del problema llamado partición con guillotina, en el que los cortes deben ser cortes de guillotina (cortes de borde a borde).
• Varios esquema de aproximación de tiempo polinómico utilizan sofisticados cortes de guillotina.[10]​[11]​[5]​

Minimizar el número de espacios en blanco

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. Se conocen los siguientes resultados:[12]​

• Si el polígono grande es un rectángulo, entonces en cualquier disposición máxima de n rectángulos, todos los agujeros son rectángulos y su número es como máximo ${\displaystyle n-\lceil 2{\sqrt {n}}-1\rceil }$, lo que se trata de una solución ajustada.
• Si el polígono grande es un polígono rectilíneo con T vértices especulares, entonces en cualquier disposición máxima de n rectángulos, los agujeros se pueden dividir en como máximo ${\displaystyle T+n-\lceil 2{\sqrt {n}}-1\rceil }$ rectángulos, lo que también se trata de una solución ajustada.

Dividir un polígono en trapecios

En los sistemas de procesamiento de imágenes a VLSI, a menudo es necesario dividir una región poligonal en el número mínimo de trapecios, con dos lados horizontales. Un triángulo de lado horizontal se considera un trapezoide de dos lados horizontales, uno de los cuales es degenerado. Para un polígono sin agujeros con ${\displaystyle n}$ lados, se puede encontrar una partición más pequeña en el tiempo ${\displaystyle O(n^{2})}$.[13]​

Si el número de trapecios no tiene por qué ser mínimo, se puede encontrar una solución trapezoidal en el tiempo ${\displaystyle O(n)}$, como subproducto de un algoritmo de triangulación de un polígono.[14]​

Si el polígono contiene agujeros, el problema es NP-completo, pero se puede encontrar una aproximación de 3 en el tiempo ${\displaystyle O(n\log n)}$.[13]​

Dividir un polígono en cuadriláteros convexos

Una cuadrilateralización o una cuadrangulación es una partición en cuadriláteros.

Una característica recurrente de los problemas de cuadrangulación es si se permiten puntos de Steiner, es decir, si el algoritmo puede sumar puntos que no sean vértices del polígono. 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.

Existen algoritmos de tiempo lineal para cuadrangulaciones de polígonos sin agujeros con puntos de Steiner, pero no se garantiza que encuentren una partición más pequeña.[15]​[16]​

Dividir un polígono en m-gonos

Una generalización de los problemas anteriores es la partición en polígonos que tienen exactamente m lados, o como máximo m lados. 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]​

Dividir un polígono en polígonos convexos

Al dividir un polígono general en polígonos convexos se han estudiado varios objetivos.

Minimizar el número de componentes

El problema de partición convexa óptimo es dividir un polígono no convexo en la menor cantidad posible de polígonos convexos, utilizando solo los vértices del polígono inicial. Existen algoritmos exactos y aproximados para este problema.[19]​

Minimizar el número de espacios en blanco

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. Si el polígono grande es convexo, entonces en cualquier disposición máxima de n figuras convexas, todos los agujeros son convexos y su número es como máximo ${\displaystyle 2n-5}$, lo que se trata de una solución ajustada.[12]​

Igualar el área y el perímetro

El problema de "partición justa de polígonos"[20]​ consiste en dividir un polígono (convexo) en piezas (convexas) con un perímetro igual y un área igual (este es un caso especial del corte de pastel justo). Cualquier polígono convexo se puede cortar fácilmente en cualquier número n de piezas convexas con un área de exactamente 1/n. Sin embargo, garantizar que las piezas tengan igual área y perímetro igual es más difícil. Existen algoritmos para resolver este problema cuando el número de piezas es una potencia de 2.[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. Este problema fue estudiado para 2 y 3 piezas.[22]​

Existe una generalización adicional para manejar cualquier número de medidas.

Formas de componentes más generales

Se han estudiado formas más generales de piezas, entre ellas: formas espirales, en estrella y polígonos monótonos. Consúltese el trabajo de J. Mark Keil[1]​ para ver desarrollos al respecto.

Véase también

• Recubrimiento de un polígono – un problema relacionado en el que se permite que las piezas se superpongan.
• Problema de empaquetado – un problema relacionado en el que las piezas tienen que caber dentro de todo el objeto grande pero no tienen que cubrirlo por completo.
• Teselado regular – un problema de dividir todo el plano en polígonos simples como rectángulos.
• Cuadratura del cuadrado – un problema de dividir un cuadrado de lados de longitud entera mediante cuadrados distintos también de lados de longitud entera.
• Particionado del espacio
• Rompecabezas de teselado: un rompecabezas que consiste en empaquetar varias piezas determinadas en un polígono más grande determinado.
• Partición con guillotina

Referencias

1. Mark Keil, J. (2000). «Polygon Decomposition». Handbook of Computational Geometry. pp. 491–518. ISBN 9780444825377. doi:10.1016/B978-044482537-7/50012-7. 
2. Eppstein, David (2010). «Graph-Theoretic Solutions to Computational Geometry Problems». Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science 5911. pp. 1-16. ISBN 978-3-642-11408-3. S2CID 16353114. doi:10.1007/978-3-642-11409-0_1. «citeseerx: 10.1.1.249.5965». 
3. Realz Slaw. «Tiling an orthogonal polygon with squares». CS stack exchange. Consultado el 19 de octubre de 2015. 
4. Andrzej Lingas and Ron Y Pinter and Ron L Rivest and Adi Shamir (1982). «Minimum edge length partitioning of rectilinear polygons». Proc. 20th Allerton Conf. Commun. Control Comput: 53-63. 
5. Du, Ding-Zhu; Ko, Ker-I.; Hu, Xiaodong (2012). Design and Analysis of Approximation Algorithms. Springer Optimization and Its Applications (en inglés). New York: Springer-Verlag. pp. 165-209, chapter 5 "guillotine cut". ISBN 978-1-4614-1700-2. 
6. Gonzalez, Teofilo; Zheng, Si-Qing (1 de junio de 1985). «Bounds for partitioning rectilinear polygons». Proceedings of the first annual symposium on Computational geometry - SCG '85. SCG '85. Baltimore, Maryland, USA: Association for Computing Machinery. pp. 281-287. ISBN 978-0-89791-163-4. S2CID 12588297. doi:10.1145/323233.323269. 
7. Levcopoulos, C (1 de agosto de 1986). «Fast heuristics for minimum length rectangular partitions of polygons». Proceedings of the second annual symposium on Computational geometry - SCG '86. SCG '86. Yorktown Heights, New York, USA: Association for Computing Machinery. pp. 100-108. ISBN 978-0-89791-194-8. S2CID 16106423. doi:10.1145/10515.10526. 
8. Gonzalez, Teofilo F.; Razzazi, Mohammadreza; Zheng, Si-Qing (1 de diciembre de 1993). «An efficient divide-and-conquer approximation algorithm for partitioning into d-boxes». International Journal of Computational Geometry & Applications 03 (4): 417-428. ISSN 0218-1959. doi:10.1142/S0218195993000269. 
9. Gonzalez, Teofilo; Zheng, Si-Qing (1 de junio de 1989). «Improved bounds for rectangular and guillotine partitions». Journal of Symbolic Computation (en inglés) 7 (6): 591-610. ISSN 0747-7171. doi:10.1016/S0747-7171(89)80042-2. 
10. Arora, S. (October 1996). «Polynomial time approximation schemes for Euclidean TSP and other geometric problems». Proceedings of 37th Conference on Foundations of Computer Science. pp. 2-11. ISBN 0-8186-7594-2. S2CID 1499391. doi:10.1109/SFCS.1996.548458. 
11. Mitchell, Joseph S. B. (1 de enero de 1999). «Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems». SIAM Journal on Computing 28 (4): 1298-1309. ISSN 0097-5397. doi:10.1137/S0097539796309764. 
12. Akopyan, Arseniy; Segal-Halevi, Erel (1 de enero de 2018). «Counting Blanks in Polygonal Arrangements». SIAM Journal on Discrete Mathematics 32 (3): 2242-2257. ISSN 0895-4801. S2CID 123397485. arXiv:1604.00960. doi:10.1137/16M110407X. 
13. Asano, Takao; Asano, Tetsuo; Imai, Hiroshi (1986). «Partitioning a polygonal region into trapezoids». Journal of the ACM 33 (2): 290. S2CID 15296037. doi:10.1145/5383.5387. hdl:2433/98478. 
14. Chazelle, Bernard (2007). «Triangulating a simple polygon in linear time». Discrete & Computational Geometry 6 (3): 485-524. doi:10.1007/bf02574703. 
15. H. Everett; W. Lenhart; M. Overmars; T. Shermer; J. Urrutia. (1992). «Strictly convex quadrilateralizations of polygons». Proc. 4th Canad. Conf. Comput. Geom. pp. 77-83. 
16. Ramaswami, Suneeta; Ramos, Pedro; Toussaint, Godfried (1998). «Converting triangulations to quadrangulations». Computational Geometry 9 (4): 257. doi:10.1016/s0925-7721(97)00019-9. 
17. Lingas, Andrzej; Levcopoulos, Christos; Sack, Jörg (1987). «Algorithms for minimum length partitions of polygons». BIT 27 (4): 474. S2CID 30936524. doi:10.1007/bf01937272. 
18. Levcopoulos, Christos; Lingas, Andrzej; Sack, Jörg-R. (1989). «Heuristics for optimum binary search trees and minimum weight triangulation problems». Theoretical Computer Science 66 (2): 181. doi:10.1016/0304-3975(89)90134-5. 
19. Hertel, Stefan; Mehlhorn, Kurt (1983). «Fast triangulation of simple polygons». En Karpinski, Marek, ed. Foundations of Computation Theory. Lecture Notes in Computer Science (en inglés) (Berlin, Heidelberg: Springer) 158: 207-218. ISBN 978-3-540-38682-7. doi:10.1007/3-540-12689-9_105. 
20. Nandakumar, R.; Rao, N. Ramana (August 2012). «'Fair' Partitions of Polygons - an Introduction». Proceedings - Mathematical Sciences 122 (3): 459-467. ISSN 0253-4142. S2CID 189909962. arXiv:0812.2241. doi:10.1007/s12044-012-0076-5. 
21. Armaselu, Bogdan; Daescu, Ovidiu (23 de noviembre de 2015). «Algorithms for fair partitioning of convex polygons». Theoretical Computer Science (en inglés) 607: 351-362. ISSN 0304-3975. doi:10.1016/j.tcs.2015.08.003. 
22. Bespamyatnikh, Sergei (2003). «On Partitioning a Cake». En Akiyama, Jin; Kano, Mikio, eds. Discrete and Computational Geometry. Lecture Notes in Computer Science (en inglés) (Berlin, Heidelberg: Springer) 2866: 60-71. ISBN 978-3-540-44400-8. doi:10.1007/978-3-540-44400-8_7. 

• Datos: Q25304242