Partición poligonal

Conjunto de formas básicas que se ensamblan para formar 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 da como resultado el polígono. Un problema de partición de polígono es un problema de búsqueda de una partición que sea mínima en algún sentido, por ejemplo, una partición con el menor número de unidades o con unidades con la menor longitud total de lado.

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

El término descomposición de polígonos se utiliza a menudo como un término general que incluye tanto la cobertura como la partición de polígonos . ^[1]

Aplicaciones

La descomposición poligonal se aplica en varias áreas: ^[1]

• Las técnicas de reconocimiento de patrones extraen información de un objeto para 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 usar esta información para determinar la forma del objeto.
• En el procesamiento de datos de diseño gráfico VLSI , los diseños se representan como polígonos y un enfoque de preparación para la litografía por haz de electrones consiste en descomponer estas regiones poligonales en figuras fundamentales. La descomposición poligonal también se utiliza en el proceso de división de la región de enrutamiento en canales.
• En geometría computacional , los algoritmos para resolver problemas con 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 del punto en el polígono es un ejemplo. Una estrategia para resolver algunos de estos tipos de problemas con polígonos generales es descomponer el polígono en partes componentes simples, resolver el problema en cada componente utilizando un algoritmo especializado y luego combinar las soluciones parciales.
• Otras aplicaciones incluyen compresión de datos , sistemas de bases de datos , procesamiento de imágenes y gráficos por computadora .

Dividir un polígono en triángulos

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

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

Partición de un polígono en pseudotriángulos

Se estudiaron las mismas dos variantes del problema para el caso en que las piezas deberían ser pseudotriángulos , es decir, polígonos que, al igual que los triángulos, tienen exactamente tres vértices convexos. Las variantes son: la partición en un número mínimo de pseudotriángulos y la partición en pseudotriángulos con una longitud total de arista mínima.

Partición de 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 rectilíneo (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 VLSI , 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 microarrays de ADN . Las particiones rectangulares pueden simplificar las operaciones de convolución en el procesamiento de imágenes y se pueden utilizar para comprimir imágenes de mapa de bits . Se han aplicado problemas de descomposición de matrices estrechamente relacionados a la planificación de radioterapia , y las particiones rectangulares también se han utilizado para diseñar secuencias de autoensamblaje de robots . ^[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 de tiempo polinómico. Véase ^{[1] : 10–13} y ^{[2] : 3–5} para encuestas.

El problema de particionar un polígono rectilíneo en un número menor de cuadrados (en contraste con rectángulos arbitrarios) es NP-difícil . ^[3]

Minimizar la longitud total del borde

En algunas aplicaciones, es más importante minimizar la longitud total de los cortes (por ejemplo, para minimizar el costo de realizar la partición o para minimizar la cantidad de polvo). Este problema se llama partición rectangular de longitud de borde mínima . 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.

Si el polígono en bruto no tiene agujeros , entonces se puede encontrar una partición óptima en tiempo , 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 . ^[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 candidatos para un segmento de línea en una partición óptima, y ​​se pueden verificar de manera eficiente utilizando programación dinámica. ^{[5] : 166–167} ${\displaystyle O(n^{4})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle O(n^{2})}$

Si el polígono en bruto puede tener agujeros , incluso si son agujeros degenerados (es decir, puntos únicos), el problema es NP-hard. Esto se puede demostrar mediante reducción a partir de Planar SAT . ^{[4] [6]} Para el caso en el que todos los agujeros son puntos únicos, se han desarrollado varias aproximaciones de factor constante:

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

Minimizar el número de espacios en blanco

En este contexto, el polígono grande ya contiene algunos rectángulos disjuntos 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 lo más pequeño 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 , y esto es estricto. ${\displaystyle n-\lceil 2{\sqrt {n}}-1\rceil }$
• Si el polígono grande es un polígono rectilíneo con T vértices reflejos, entonces en cualquier disposición máxima de n rectángulos, los agujeros se pueden dividir en, como máximo, rectángulos, y esto es estricto. ${\displaystyle T+n-\lceil 2{\sqrt {n}}-1\rceil }$

Dividir un polígono en trapecios

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

Si el número de trapecios no necesita ser mínimo, se puede encontrar una trapezoidalidad en el tiempo , como un subproducto de un algoritmo de triangulación de polígonos . ^[14] ${\displaystyle O(n)}$

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

Dividir un polígono en cuadriláteros convexos

Una cuadriláteratación o 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 se permite que el algoritmo agregue 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 la partición más pequeña. ^{[15] [16]}

Dividir un polígono enmetro-gones

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 un polinomio de tiempo 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 óptimo de partición convexa consiste en dividir un polígono no convexo en la menor cantidad posible de polígonos convexos , utilizando únicamente 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 una 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 , y esto es ajustado. ^[12] ${\displaystyle 2n-5}$

Igualando el área y el perímetro

El problema de partición justa de polígonos ^[20] consiste en dividir un polígono (convexo) en partes (convexas) con un perímetro y un área iguales (este es un caso especial de partición justa ). Cualquier polígono convexo se puede cortar fácilmente en cualquier número n de partes convexas con un área de exactamente 1/ n . Sin embargo, garantizar que las partes tengan áreas y perímetros iguales es más difícil. Existen algoritmos para resolver este problema cuando el número de partes es una potencia de 2. ^[21]

Una generalización de este problema es cuando las medidas del área y del perímetro se reemplazan por una medida en el cuerpo y en el borde del polígono, respectivamente. Este problema se estudió 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 , polígonos estrellados y polígonos monótonos . Véase ^[1] para una descripción general.

Véase también

• Recubrimiento de polígonos : un problema relacionado en el que se permite que las piezas se superpongan.
• Problema de embalaje : un problema relacionado en el que las piezas tienen que caber dentro de todo el objeto grande, pero no tienen que cubrirlo por completo.
• Teselación euclidiana mediante polígonos regulares convexos : un problema de partición de todo el plano en polígonos simples como rectángulos .
• Cuadrar el cuadrado : problema de dividir un cuadrado integral utilizando únicamente otros cuadrados integrales.
• Partición del espacio
• Rompecabezas de mosaicos : un rompecabezas que consiste en agrupar varias piezas dadas en un polígono determinado más grande.
• Partición de guillotina

Referencias

1. Mark Keil, J. (2000). "Descomposición de polígonos". Manual de geometría computacional . págs. 491–518. doi :10.1016/B978-044482537-7/50012-7. ISBN 9780444825377.
2. Eppstein, David (2010). "Soluciones grafo-teóricas para problemas de geometría computacional". Conceptos grafo-teóricos en informática . Apuntes de clase en informática. Vol. 5911. págs. 1–16. CiteSeerX 10.1.1.249.5965 . doi :10.1007/978-3-642-11409-0_1. ISBN  978-3-642-11408-3. Número de identificación del sujeto  16353114.
3. Realz Slaw. "Teselación de un polígono ortogonal con cuadrados". CS Stack Exchange . Consultado el 19 de octubre de 2015 .
4. Andrzej Lingas y Ron Y Pinter y Ron L Rivest y Adi Shamir (1982). "Particionado de polígonos rectilíneos por longitud mínima de arista" (PDF) . Proc. 20th Allerton Conf. Commun. Control Comput : 53–63.
5. 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.
6. Gonzalez, Teofilo; Zheng, Si-Qing (1985-06-01). "Límites para la partición de polígonos rectilíneos". Actas del primer simposio anual sobre geometría computacional - SCG '85 . Baltimore, Maryland, EE. UU.: Association for Computing Machinery. págs. 281–287. doi :10.1145/323233.323269. ISBN 978-0-89791-163-4. Número de identificación del sujeto  12588297.
7. Levcopoulos, C (1986-08-01). "Heurísticas rápidas para particiones rectangulares de polígonos de longitud mínima". Actas del segundo simposio anual sobre geometría computacional - SCG '86 . Yorktown Heights, Nueva York, EE. UU.: Association for Computing Machinery. págs. 100–108. doi : 10.1145/10515.10526 . ISBN . 978-0-89791-194-8.S2CID16106423  .​
8. Gonzalez, Teofilo F.; Razzazi, Mohammadreza; Zheng, Si-Qing (1993-12-01). "Un algoritmo eficiente de aproximación de divide y vencerás para la partición en d-boxes". Revista Internacional de Geometría Computacional y Aplicaciones . 03 (4): 417–428. doi :10.1142/S0218195993000269. ISSN  0218-1959.
9. 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.
10. Arora, S. (octubre de 1996). "Esquemas de aproximación temporal polinómica para problemas geométricos de transición de tiempo euclidiano y otros". 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.S2CID1499391  .​
11. 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 de TSP, k-MST y relacionados". Revista SIAM de informática . 28 (4): 1298–1309. doi :10.1137/S0097539796309764. ISSN  0097-5397.
12. Akopyan, Arseniy; Segal-Halevi, Erel (1 de enero de 2018). "Conteo de espacios en blanco en arreglos poligonales". Revista SIAM de Matemáticas Discretas . 32 (3): 2242–2257. arXiv : 1604.00960 . doi :10.1137/16M110407X. ISSN  0895-4801. S2CID  123397485.
13. Asano, Takao; Asano, Tetsuo; Imai, Hiroshi (1986). "Partición de una región poligonal en trapecios". Revista de la ACM . 33 (2): 290. doi :10.1145/5383.5387. hdl : 2433/98478 . S2CID  15296037.
14. Chazelle, Bernard (2007). "Triangulación de un polígono simple en tiempo lineal". Geometría discreta y computacional . 6 (3): 485–524. doi : 10.1007/bf02574703 .
15. H. Everett; W. Lenhart; M. Overmars; T. Shermer; J. Urrutia. (1992). "Cuadrilateralizaciones estrictamente convexas de polígonos". Proc. 4th Canad. Conf. Comput. Geom . pp. 77–83.
16. Ramaswami, Suneeta; Ramos, Pedro; Toussaint, Godfried (1998). "Conversión de triangulaciones en cuadrangulaciones". Geometría Computacional . 9 (4): 257. doi : 10.1016/s0925-7721(97)00019-9 .
17. Lingas, Andrzej; Levcopoulos, Christos; Sack, Jörg (1987). "Algoritmos para particiones de longitud mínima de polígonos". BIT . 27 (4): 474. doi :10.1007/bf01937272. S2CID  30936524.
18. Levcopoulos, Christos; Lingas, Andrzej; Sack, Jörg-R. (1989). "Heurísticas para árboles de búsqueda binaria óptimos y problemas de triangulación de peso mínimo". Ciencias de la Computación Teórica . 66 (2): 181. doi : 10.1016/0304-3975(89)90134-5 .
19. Hertel, Stefan; Mehlhorn, Kurt (1983). "Triangulación rápida de polígonos simples". En Karpinski, Marek (ed.). Fundamentos de la teoría de la computación. Apuntes de clase en informática. Vol. 158. Berlín, Heidelberg: Springer. págs. 207–218. doi :10.1007/3-540-12689-9_105. ISBN 978-3-540-38682-7.
20. Nandakumar, R.; Rao, N. Ramana (agosto de 2012). "Particiones 'justas' de polígonos: una introducción". Actas - Ciencias matemáticas . 122 (3): 459–467. arXiv : 0812.2241 . doi :10.1007/s12044-012-0076-5. ISSN  0253-4142. S2CID  189909962.
21. Armaselu, Bogdan; Daescu, Ovidiu (23 de noviembre de 2015). "Algoritmos para la partición justa de polígonos convexos". Ciencias de la Computación Teórica . 607 : 351–362. doi : 10.1016/j.tcs.2015.08.003 . ISSN  0304-3975.
22. Bespamyatnikh, Sergei (2003). "Sobre la partición de un pastel". En Akiyama, Jin; Kano, Mikio (eds.). Geometría discreta y computacional: Conferencia japonesa, JCDCG 2002, Tokio, Japón, 6-9 de diciembre de 2002, Documentos revisados . Apuntes de clase en informática. Vol. 2866. Berlín, Heidelberg: Springer. págs. 60-71. doi :10.1007/978-3-540-44400-8_7. ISBN 978-3-540-44400-8.