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 al polígono. Un problema de partición poligonal es un problema de encontrar una partición que sea mínima en algún sentido, por ejemplo, una partición con un número mínimo 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 que se particione y los tipos de unidades permitidas en la partición.
El término descomposición poligonal se usa a menudo como un término general que incluye tanto la cobertura como la 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 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 ilustraciones de VLSI , los diseños se representan como polígonos, y un enfoque para la 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 usa en el proceso de dividir la región de enrutamiento en canales.
- En geometría computacional , los algoritmos para problemas en polígonos generales suelen ser más complejos que los de tipos restringidos de polígonos, como convexos o en forma de estrella. El problema de la inclusión de puntos es un ejemplo. Una estrategia para resolver algunos de estos tipos de problemas en polígonos generales es descomponer el polígono en partes componentes simples, resolver el problema en cada componente usando 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 .
Partición de 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, una triangulación se puede calcular en el tiempo . Para un polígono con agujeros, hay un límite inferior de.
Un problema relacionado es la división en triángulos con una longitud de borde total mínima, también llamada triangulación de peso mínimo .
Partición de un polígono en pseudo-triángulos
Se estudiaron 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ínimo de pseodutriángulos y dividir en pseudotriángulos con una longitud de borde total 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 matriz estrechamente relacionados a la planificación de la radioterapia , y también se han utilizado particiones rectangulares 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 polinomial: se conocen varios algoritmos de tiempo polinomial. Consulte [1] : 10–13 y [2] : 3–5 para las encuestas.
El problema de dividir un polígono rectilíneo en un número mínimo de cuadrados (en contraste con los 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 denomina 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 del tiempo de ejecución de este problema depende crucialmente de si se permite que el polígono sin procesar tenga agujeros.
Si el polígono sin procesar no tiene huecos , entonces se puede encontrar una partición óptima a 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 usa programación dinámica y se basa en el siguiente hecho: si el polígono no tiene huecos, 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 se puede "empujar" hasta que llegue a uno de los vértices del límite, sin cambiar la longitud total. Por lo tanto, solo haycandidatos para un segmento de línea en una partición óptima, y se pueden verificar de manera eficiente mediante la programación dinámica. [5] : 166–167
Si el polígono sin procesar puede tener huecos , incluso si son huecos degenerados (es decir, puntos únicos), el problema es NP-hard. Esto puede demostrarse mediante la reducción de Planar SAT . [4] [6] Para el caso en el que todos los huecos son puntos únicos, se han desarrollado varias aproximaciones de factores constantes:
- Aproximación a (3 + sqrt (3)) en el tiempo ; [6]
- Aproximación a (3 + sqrt (3)) en el tiempo ; [7]
- Una aproximación de 4 aproximaciones en el tiempo (más generalmente, en d dimensiones, es un aproximación en el tiempo ), [8]
- Una aproximación 3 en el tiempo ;
- Una aproximación de 1,75 en el tiempo (más generalmente, en d dimensiones, es un aproximación en el tiempo ); [9] la última aproximación utiliza una variante restringida del problema llamado partición de guillotina , en el que los cortes deben ser cortes de guillotina ( cortes de borde a borde).
- Varios esquemas de aproximación de tiempo polinomial utilizando sofisticados cortes de guillotina. [10] [11] [5]
Partición de un polígono en trapezoides
En los sistemas de procesamiento de ilustraciones VLSI, a menudo se requiere dividir una región poligonal en el número mínimo de trapezoides , con dos lados horizontales. Un triángulo con un lado horizontal se considera un trapezoide con dos lados horizontales, uno de los cuales está degenerado. Para un polígono sin agujeros con lados, una partición de este tipo más pequeña se puede encontrar en el tiempo . [12]
Si el número de trapezoides no necesita ser mínimo, se puede encontrar una trapezoidación a tiempo , como un subproducto de un algoritmo de triangulación de polígonos . [13]
Si el polígono contiene huecos, el problema es NP-completo, pero se puede encontrar una aproximación de 3 en el tiempo . [12]
Divide un polígono en cuadriláteros convexos
Una cuadrilátero 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 agregar puntos que no son vértices del polígono. Permitir puntos Steiner puede permitir divisiones más pequeñas, pero luego 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 huecos con puntos Steiner, pero no se garantiza que encuentren la partición más pequeña. [14] [15]
Partición de un polígono en m -gones
Una generalización de los problemas anteriores es la división en polígonos que tienen exactamente m lados, o como máximo m lados. Aquí el objetivo es minimizar la longitud total del borde. Este problema se puede resolver en polinomios de tiempo en n y m . [16] [17]
Partición de un polígono en polígonos convexos
El problema óptimo de partición convexa 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. [18]
Formas de componentes más generales
Se han estudiado formas más generales de piezas, incluyendo: formas espirales , polígonos en estrella y polígonos monótonos . Consulte [1] para ver una encuesta.
Divida un polígono convexo en piezas convexas con igual área y perímetro
El problema de la división de polígonos justos [19] es dividir un polígono (convexo) en piezas (convexas) con un perímetro y un área iguales (este es un caso especial de corte de torta 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, es más difícil asegurarse de que las piezas tengan el mismo área y el mismo perímetro. Existen algoritmos para resolver este problema cuando el número de piezas es una potencia de 2. [20]
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 se estudió para 2 y 3 piezas. [21]
Hay una generalización adicional para manejar cualquier número de medidas.
Ver también
- Revestimiento poligonal : 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.
- Mosaicos euclidianos por polígonos regulares convexos : un problema de dividir todo el plano en polígonos simples como rectángulos .
- Cuadrar el cuadrado : un problema de dividir un cuadrado integral usando solo otros cuadrados integrales.
- Partición del espacio
- Rompecabezas de mosaico : un rompecabezas que consiste en empaquetar varias piezas dadas en un polígono mayor dado.
- Partición de guillotina
Referencias
- ↑ a b c d e f 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.
- ^ a b c Eppstein, David (2010). "Soluciones gráficas teóricas a problemas de geometría computacional". Conceptos teóricos de grafos en informática . Apuntes de conferencias en Ciencias de la Computación. 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. S2CID 16353114 .
- ^ Realz Slaw. "Mosaico de un polígono ortogonal con cuadrados" . Intercambio de pila CS . Consultado el 19 de octubre de 2015 .
- ^ a b c Andrzej Lingas y Ron Y Pinter y Ron L Rivest y Adi Shamir (1982). "Partición de longitud de borde mínima de polígonos rectilíneos" (PDF) . Proc. 20ª Conf. Allerton Comun. Computación de control : 53–63.
- ^ a b c 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. pp. 165-209, capítulo 5 "corte de guillotina". ISBN 978-1-4614-1700-2.
- ^ a b González, Teófilo; Zheng, Si-Qing (1 de junio de 1985). "Límites para particionar polígonos rectilíneos" . Actas del primer simposio anual sobre geometría computacional . SCG '85. Baltimore, Maryland, EE. UU.: Asociación de Maquinaria de Computación: 281–287. doi : 10.1145 / 323233.323269 . ISBN 978-0-89791-163-4. S2CID 12588297 .
- ^ Levcopoulos, C (1 de agosto de 1986). "Heurística rápida para particiones rectangulares de longitud mínima de polígonos" . Actas del Segundo Simposio Anual sobre Geometría Computacional . SCG '86. Yorktown Heights, Nueva York, EE. UU.: Association for Computing Machinery: 100–108. doi : 10.1145 / 10515.10526 . ISBN 978-0-89791-194-8. S2CID 16106423 .
- ^ González, Teófilo F .; Razzazi, Mohammadreza; Zheng, Si-Qing (1 de diciembre de 1993). "Un algoritmo de aproximación de divide y vencerás eficiente para la partición en d-boxes" . Revista Internacional de Geometría y Aplicaciones Computacionales . 03 (4): 417–428. doi : 10.1142 / S0218195993000269 . ISSN 0218-1959 .
- ^ González, Teófilo; Zheng, Si-Qing (1 de junio de 1989). "Límites mejorados para particiones rectangulares y de guillotina" . Revista de Computación Simbólica . 7 (6): 591–610. doi : 10.1016 / S0747-7171 (89) 80042-2 . ISSN 0747-7171 .
- ^ Arora, S. (octubre de 1996). "Esquemas de aproximación de tiempo polinomial para TSP euclidiana y otros problemas geométricos" . Actas de la 37ª Conferencia sobre los fundamentos de la informática : 2-11. doi : 10.1109 / SFCS.1996.548458 . ISBN 0-8186-7594-2. S2CID 1499391 .
- ^ Mitchell, Joseph SB (1 de enero de 1999). "Subdivisiones de guillotina subdivisiones poligonales aproximadas: un esquema de aproximación de polinomio-tiempo simple para TSP geométrica, k-MST y problemas relacionados" . Revista SIAM de Computación . 28 (4): 1298-1309. doi : 10.1137 / S0097539796309764 . ISSN 0097-5397 .
- ^ a b c Asano, Takao; Asano, Tetsuo; Imai, Hiroshi (1986). "Partición de una región poligonal en trapezoides". Revista de la ACM . 33 (2): 290. doi : 10.1145 / 5383.5387 . hdl : 2433/98478 . S2CID 15296037 .
- ^ Chazelle, Bernard (2007). "Triangular un polígono simple en tiempo lineal" . Geometría discreta y computacional . 6 (3): 485–524. doi : 10.1007 / bf02574703 .
- ^ H. Everett; W. Lenhart; M. Overmars; T. Shermer; J. Urrutia. (1992). "Cuadriláteros estrictamente convexos de polígonos". Proc. 4th Canad. Conf. Computación. Geom . págs. 77–83.
- ^ Ramaswami, Suneeta; Ramos, Pedro; Toussaint, Godfried (1998). "Convertir triangulaciones en cuadrangulaciones". Geometría computacional . 9 (4): 257. doi : 10.1016 / s0925-7721 (97) 00019-9 .
- ^ 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 .
- ^ Levcopoulos, Christos; Lingas, Andrzej; Saco, Jörg-R. (1989). "Heurísticas para árboles de búsqueda binarios óptimos y problemas de triangulación de peso mínimo". Informática Teórica . 66 (2): 181. doi : 10.1016 / 0304-3975 (89) 90134-5 .
- ^ Hertel, Stefan; Mehlhorn, Kurt (1983). Karpinski, Marek (ed.). "Triangulación rápida de polígonos simples" . Fundamentos de la teoría de la computación . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 158 : 207–218. doi : 10.1007 / 3-540-12689-9_105 . ISBN 978-3-540-38682-7.
- ^ 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 .
- ^ Armaselu, Bogdan; Daescu, Ovidiu (23 de noviembre de 2015). "Algoritmos para la partición equitativa de polígonos convexos" . Informática Teórica . 607 : 351–362. doi : 10.1016 / j.tcs.2015.08.003 . ISSN 0304-3975 .
- ^ Bespamyatnikh, Sergei (2003). Akiyama, Jin; Kano, Mikio (eds.). "Sobre la partición de un pastel" . Geometría discreta y computacional . Apuntes de conferencias en Ciencias de la Computación. Berlín, Heidelberg: Springer. 2866 : 60–71. doi : 10.1007 / 978-3-540-44400-8_7 . ISBN 978-3-540-44400-8.
- ^ Lingas, Andrzej (1982). "El poder de los agujeros no rectilíneos". Autómatas, lenguajes y programación . Apuntes de conferencias en Ciencias de la Computación. 140 . págs. 369–383. doi : 10.1007 / bfb0012784 . ISBN 978-3-540-11576-2.