En geometría computacional y ciencias de la computación , el problema de triangulación de peso mínimo es el problema de encontrar una triangulación de longitud de borde total mínima. [1] Es decir, un polígono de entrada o el casco convexo de un conjunto de puntos de entrada debe subdividirse en triángulos que se encuentren de borde a borde y de vértice a vértice, de tal manera que se minimice la suma de los perímetros de los triángulos. El problema es NP-difícil para las entradas de conjuntos de puntos, pero puede aproximarse a cualquier grado deseado de precisión. Para las entradas de polígono, se puede resolver exactamente en tiempo polinomial. La triangulación de peso mínimo también se ha denominado a veces triangulación óptima..
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/0/0f/Convex_Polygon_triangulations.svg/300px-Convex_Polygon_triangulations.svg.png)
Historia
El problema de la triangulación de peso mínimo de un conjunto de puntos fue planteado por Düppe & Gottschalk (1970) , quienes sugirieron su aplicación a la construcción de modelos de redes irregulares trianguladas de contornos terrestres, y utilizaron una heurística codiciosa para aproximarlo. Shamos y Hoey (1975) conjeturaron que la triangulación de peso mínimo siempre coincidía con la triangulación de Delaunay , pero esto fue rápidamente refutado por Lloyd (1977) , y de hecho Kirkpatrick (1980) mostró que los pesos de las dos triangulaciones pueden diferir por un factor lineal. . [2]
El problema de la triangulación de peso mínimo se hizo notorio cuando Garey y Johnson (1979) lo incluyeron en una lista de problemas abiertos en su libro sobre NP-completitud , y muchos autores posteriores publicaron resultados parciales al respecto. Finalmente, Mulzer y Rote (2008) demostraron que es NP-duro, y Remy y Steger (2009) demostraron que se pueden construir de manera eficiente aproximaciones precisas.
Complejidad
El peso de una triangulación de un conjunto de puntos en el plano euclidiano se define como la suma de las longitudes de sus bordes. Su variante de decisión es el problema de decidir si existe una triangulación de peso menor que un peso dado; que fue demostrado ser NP-duro por Mulzer y Rote (2008) . Su prueba es por reducción de PLANAR-1-IN-3-SAT, un caso especial del problema de satisfacibilidad booleano en el que un 3-CNF cuya gráfica es plana se acepta cuando tiene una asignación de verdad que satisface exactamente un literal en cada cláusula. . La prueba utiliza dispositivos complejos e implica asistencia informática para verificar el comportamiento correcto de estos dispositivos.
No se sabe si el problema de decisión de triangulación de peso mínimo es NP-completo , ya que esto depende del problema abierto conocido de si la suma de radicales se puede calcular en tiempo polinomial. Sin embargo, Mulzer y Rote comentan que el problema es NP-completo si los pesos de los bordes se redondean a valores enteros.
Aunque NP-hard, la triangulación de peso mínimo puede construirse en tiempo subexponencial mediante un algoritmo de programación dinámica que considera todos los posibles separadores de ciclos simples depuntos dentro de la triangulación, encuentra recursivamente la triangulación óptima en cada lado del ciclo y elige el separador de ciclo que conduce al peso total más pequeño. El tiempo total para este método es. [3]
Aproximación
Varios autores han demostrado resultados que relacionan la triangulación de peso mínimo con otras triangulaciones en términos de la relación de aproximación , la relación del peor caso entre la longitud total del borde de la triangulación alternativa y la longitud total de la triangulación de peso mínimo. En este sentido, se sabe que la triangulación de Delaunay tiene una razón de aproximación de, [4] y que la triangulación codiciosa (la triangulación formada agregando bordes en orden de más corto a más largo, en cada paso incluyendo un borde siempre que no cruce un borde anterior) tiene una relación de aproximación de. [5] No obstante, para conjuntos de puntos distribuidos aleatoriamente, tanto las triangulaciones de Delaunay como las codiciosas están dentro de un factor logarítmico del peso mínimo. [6]
El resultado de dureza de Mulzer y Rote también implica la dureza NP de encontrar una solución aproximada con un error de aproximación relativo como máximo O (1 / n 2 ). Por lo tanto, es poco probable un esquema de aproximación completamente polinomial para la triangulación de peso mínimo. Sin embargo, es posible un esquema de aproximación cuasi-polinomial: para cualquier constante ε 0, se puede encontrar una solución con una relación de aproximación 1 + ε en el tiempo cuasi-polinomial exp (O ((log n ) 9 ). [7]
Heurísticas
Debido a la dificultad de encontrar las soluciones exactas de la triangulación de peso mínimo, muchos autores han estudiado heurísticas que en algunos casos pueden encontrar la solución, aunque no se puede probar que funcionen en todos los casos. En particular, gran parte de esta investigación se ha centrado en el problema de encontrar conjuntos de aristas que estén garantizadas para pertenecer a la triangulación de peso mínimo. Si un subgrafo de la triangulación de peso mínimo encontrado de esta manera resulta estar conectado, entonces el espacio no triangulado restante puede verse como formando un polígono simple, y la triangulación completa se puede encontrar usando programación dinámica para encontrar la triangulación óptima de este espacio poligonal. El mismo enfoque de programación dinámica también se puede extender al caso de que el subgrafo tenga un número limitado de componentes conectados [8] y el mismo enfoque de encontrar un gráfico conectado y luego aplicar programación dinámica para llenar los espacios poligonales que rodean los bordes del gráfico tiene también se ha utilizado como parte de la heurística para encontrar triangulaciones de peso bajo pero no de peso mínimo. [9]
El gráfico formado al conectar dos puntos siempre que sean los vecinos más cercanos del otro es necesariamente un subgráfico de la triangulación de peso mínimo. [10] Sin embargo, este gráfico de vecino más cercano mutuo es una coincidencia y, por lo tanto, nunca está conectado. Una línea de investigación relacionada encuentra grandes subgráficos de la triangulación de peso mínimo utilizando esqueletos β basados en círculos , los gráficos geométricos formados al incluir un borde entre dos puntos u y v siempre que no exista un tercer punto w que forme un ángulo uwv mayor que algún parámetro θ. Se ha demostrado que, para valores suficientemente pequeños de θ, el gráfico así formado es un subgrafo de la triangulación de peso mínimo. [11] Sin embargo, la elección de θ necesaria para asegurar que esto sea menor que el ángulo {{{1}}} para el cual el esqueleto β siempre está conectado.
Dickerson y Montague (1996) propusieron una técnica más sofisticada llamada esqueleto LMT . Está formado por un proceso iterativo, en el que se mantienen dos conjuntos de aristas, un conjunto de aristas que se sabe pertenecen a la triangulación de peso mínimo y un conjunto de aristas que son candidatas a pertenecer a ella. Inicialmente, el conjunto de bordes conocidos se inicializa en el casco convexo de la entrada y todos los pares restantes de vértices forman bordes candidatos. Luego, en cada iteración del proceso de construcción, los bordes candidatos se eliminan siempre que no haya un par de triángulos formado por los bordes restantes que forman un cuadrilátero para el cual el borde candidato es la diagonal más corta, y los bordes candidatos se mueven al conjunto de bordes conocidos. cuando no hay otro margen candidato que los cruce. El esqueleto LMT se define como el conjunto de bordes conocidos producidos después de que este proceso deja de realizar más cambios. Se garantiza que es un subgrafo de la triangulación de peso mínimo, se puede construir de manera eficiente y, en experimentos en conjuntos de hasta 200 puntos, se conectó con frecuencia. [12] Sin embargo, se ha demostrado que, en promedio, para conjuntos de puntos grandes tiene un número lineal de componentes conectados. [13]
Otras heurísticas que se han aplicado al problema de triangulación de peso mínimo incluyen algoritmos genéticos [14] ramificación y unión , [15] y algoritmos de optimización de colonias de hormigas . [dieciséis]
Variaciones
Se puede construir una triangulación poligonal de peso mínimo en tiempo cúbico utilizando el enfoque de programación dinámica , informado de forma independiente por Gilbert (1979) y Klincsek (1980) . En este método, los vértices se numeran consecutivamente alrededor del límite del polígono, y para cada diagonal desde el vértice i al vértice j que se encuentra dentro del polígono, la triangulación óptima se calcula considerando todos los triángulos posibles ijk dentro del polígono, sumando los pesos de las triangulaciones óptimas por debajo de las diagonales ik y jk , y eligiendo el vértice k que conduce al peso total mínimo. Es decir, si MWT ( i , j ) denota el peso de la triangulación de peso mínimo del polígono debajo del borde ij , entonces el algoritmo general realiza los siguientes pasos:
- Para cada valor posible de i , desde n - 1 hasta 1, haga lo siguiente:
- Para cada valor posible de j , de i + 1 an , haga:
- Si ij es un borde del polígono, establezca MWT ( i , j ) = length ( ij )
- De lo contrario, si ij no es una diagonal interior del polígono, establezca MWT ( i , j ) = + ∞
- De lo contrario, establezca MWT ( i , j ) = longitud ( ij ) + min i < k < j MWT ( i , k ) + MWT ( k, j )
- Para cada valor posible de j , de i + 1 an , haga:
Una vez completada esta iteración, MWT (1, n ) almacenará el peso total de la triangulación de peso mínimo. La triangulación en sí puede obtenerse buscando recursivamente a través de esta matriz, comenzando desde MWT (1, n ), en cada paso eligiendo el triángulo ijk que conduce al valor mínimo para MWT ( i , j ) y buscando recursivamente MWT ( i , k ) y MWT ( j , k ).
Métodos de programación dinámica similares también se pueden adaptar a entradas de conjuntos de puntos donde todos menos un número constante de puntos se encuentran en el casco convexo de la entrada, [17] y a conjuntos de puntos que se encuentran en un número constante de polígonos convexos anidados o en una constante. número de líneas, de las cuales no dos cruzan dentro del casco convexo. [18]
También es posible formular una versión del conjunto de puntos o problemas de triangulación de polígonos en los que se permite agregar puntos Steiner , vértices adicionales, para reducir la longitud total del borde de las triangulaciones resultantes. En algunos casos, la triangulación resultante puede ser más corta que la triangulación de peso mínimo hasta en un factor lineal. Es posible aproximar la triangulación de Steiner de peso mínimo de un conjunto de puntos dentro de un factor constante de óptimo, pero el factor constante en la aproximación es grande. [19]
Los problemas relacionados que también se han estudiado incluyen la construcción de pseudotriangulaciones de peso mínimo [20] y la caracterización de las gráficas de triangulaciones de peso mínimo. [21]
Notas
- ^ Para encuestas sobre el problema, véanse Xu (1998) , Levcopoulos (2008) y De Loera, Rambau & Santos (2010) .
- ^ Véase también Manacher y Zobrist (1979) .
- ^ Lingas (1998) .
- ^ Kirkpatrick (1980) . Manacher y Zobrist (1979) dieron un límite más débil.
- ^ Una familia de ejemplos que demuestra que la razón de aproximación esfue proporcionado por Levcopoulos (1987) , y el límite superior coincidente es por Levcopoulos y Krznaric (1998) . Al igual que con la relación de aproximación para la triangulación de Delaunay, Manacher y Zobrist (1979) también dieron un límite más débil .
- ^ Lingas (1986) .
- ^ Remy y Steger (2009) . Para obtener resultados anteriores sobre los algoritmos de aproximación de tiempo polinómico, véanse Plaisted y Hong (1987) (aproximación de factor logarítmico) y Levcopoulos y Krznaric (1998) (aproximación de factor constante).
- ^ Cheng, Golin y Tsang (1995) .
- ^ Lingas (1987) ; Heath y Pemmaraju (1994) .
- ^ Yang, Xu y usted (1994) .
- ^ Keil (1994) ; Cheng, Golin y Tsang (1995) ; Cheng y Xu (2001) ; Hu (2010) .
- ^ Dickerson y Montague (1996) ; Cheng, Katoh y Sugai (1996) ; Beirouti y Snoeyink (1998) ; Aichholzer, Aurenhammer y Hainz (1999) .
- ^ Bose, Devroye y Evans (1996) .
- ^ Qin, Wang y Gong (1997) ; Capp y Julstrom (1998) .
- ^ Kyoda y col. (1997) .
- ^ Jahani, Bigham y Askari (2010) .
- ^ Hoffmann y Okamoto (2004) ; Grantson, Borgelt y Levcopoulos (2005) ; Knauer y Spillner (2006) .
- ^ Anagnostou y Corneil (1993) ; Meijer y Rappaport (1992) .
- ^ Eppstein (1994) .
- ^ Gudmundsson y Levcopoulos (2007) ; Aichholzer y col. (2009) .
- ^ Lenhart y Liotta (2002) .
Referencias
- Aichholzer, Oswin; Aurenhammer, Franz ; Hackl, Thomas; Speckmann, Bettina (2009), "Sobre pseudo-triangulaciones de peso mínimo", Teoría y aplicaciones de la geometría computacional , 42 (6-7): 627-631, doi : 10.1016 / j.comgeo.2008.10.002 , MR 2519380.
- Aichholzer, Oswin; Aurenhammer, Franz ; Hainz, Reinhard (1999), "New results on MWT subgraphs", Information Processing Letters , 69 (5): 215-219, doi : 10.1016 / S0020-0190 (99) 00018-6.
- Anagnostou, Efthymios; Corneil, Derek (1993), "Instancias de tiempo polinómico del problema de triangulación de peso mínimo", Geometría Computacional. Teoría y aplicaciones , 3 (5): 247–259, doi : 10.1016 / 0925-7721 (93) 90016-Y , MR 1251594.
- Beirouti, Ronald; Snoeyink, Jack (1998), "Implementaciones de la heurística LMT para la triangulación de peso mínimo", Proc. 14 ° Simposio de ACM sobre geometría computacional , págs. 96-105, doi : 10.1145 / 276884.276895.
- Bose, Prosenjit ; Devroye, Luc; Evans, William (1996), "Los diamantes no son el mejor amigo de la triangulación de peso mínimo", Proc. Octava Conferencia Canadiense sobre Geometría Computacional (CCCG 1996) (PDF) , págs. 68–73.
- Capp, Kerry; Julstrom, Bryant A. (1998), "Un algoritmo genético codificado por peso para el problema de triangulación de peso mínimo", Proc. Simposio ACM sobre Computación Aplicada , Atlanta, Georgia, Estados Unidos, págs. 327–331, doi : 10.1145 / 330560.330833 , Semantic Scholar.
- Cheng, Siu-Wing; Golin, Mordecai; Tsang, J. (1995), "Análisis de casos esperados de esqueletos β con aplicaciones a la construcción de triangulaciones de peso mínimo", Proc. Séptima Conferencia Canadiense sobre Geometría Computacional (CCCG 1995) , págs. 279–284.
- Cheng, Siu-Wing; Katoh, Naoki; Sugai, Manabu (1996), "Un estudio del esqueleto LMT", Algoritmos y Computación , Lecture Notes in Computer Science, 1178 , pp. 256-265, doi : 10.1007 / BFb0009502.
- Cheng, Siu-Wing; Xu, Yin-Feng (2001), "On β -skeleton as a subgraph of the minimal weight triangulation", Theoretical Computer Science , 262 (1–2): 459–471, doi : 10.1016 / S0304-3975 (00) 00318 -2.
- De Loera, Jesús A .; Rambau, Jörg; Santos, Francisco (2010), "3.2.3 Triangulaciones codiciosas y de peso mínimo", Triangulaciones: Estructuras para algoritmos y aplicaciones , Algoritmos y computación en matemáticas, 25 , Springer, pp. 102-107, ISBN 978-3-642-12970-4.
- Dickerson, Matthew T .; Montague, Mark H. (1996), "Un subgrafo conectado (¿generalmente?) De la triangulación de peso mínimo", Proc. 12 ° Simposio de ACM sobre geometría computacional , págs. 204–213, doi : 10.1145 / 237218.237364.
- Düppe, RD; Gottschalk, HJ (1970), "Automatische Interpolation von Isolinien bei willkürlich verteilten Stützpunkten", Allgemeine Vermessungs-Nachrichten , 77 : 423–426. Según lo citado por Mulzer & Rote (2008) y Remy & Steger (2009) .
- Eppstein, David (1994), "Aproximación de la triangulación de Steiner de peso mínimo" (PDF) , Geometría discreta y computacional , 11 (2): 163-191, doi : 10.1007 / BF02574002 , MR 1254088.
- Garey, MR ; Johnson, DS (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , San Francisco, Calif .: WH Freeman, Problem OPEN12, p. 288 , ISBN 0-7167-1045-5, MR 0519066.
- Gilbert, PD (1979), Nuevos resultados en triangulaciones planas , Informe R-850, Urbana, Illinois: Laboratorio de Ciencias Coordinado, Universidad de Illinois.
- Grantson, M .; Borgelt, C .; Levcopoulos, C. (2005), "Triangulación de peso mínimo recortando triángulos", Proc. 16º Simposio Internacional sobre Algoritmos y Computación , págs. 984–994.
- Gudmundsson, Joachim; Levcopoulos, Christos (2007), "Pseudo-triangulaciones de peso mínimo", Teoría y aplicaciones de la geometría computacional , 38 (3): 139-153, doi : 10.1016 / j.comgeo.2007.05.004 , MR 2352529.
- Heath, LS; Pemmaraju, SV (1994), "Nuevos resultados para el problema de triangulación de peso mínimo" , Algorithmica , 12 (6): 533–552, doi : 10.1007 / BF01188718 , MR 1297812.
- Hoffmann, M .; Okamoto, Y. (2004), "El problema de triangulación de peso mínimo con pocos puntos internos", Proc. 1er Taller internacional sobre computación exacta y parametrizada , págs. 200–212.
- Hu, Shiyan (2010), "Una nueva región de inclusión asimétrica para la triangulación de peso mínimo", Journal of Global Optimization , 46 (1): 63–73, CiteSeerX 10.1.1.377.6164 , doi : 10.1007 / s10898-009-9409- z , MR 2566136.
- Jahani, M .; Bigham, BS; Askari, A. (2010), "Un algoritmo de colonia de hormigas para la triangulación de peso mínimo", Conferencia internacional sobre ciencia computacional y sus aplicaciones (ICCSA) , págs. 81–85, doi : 10.1109 / ICCSA.2010.38 , Semantic Scholar.
- Keil, J. Mark (1994), "Cálculo de un subgrafo de la triangulación de peso mínimo" , Geometría computacional: teoría y aplicaciones , 4 (1): 18-26, doi : 10.1016 / 0925-7721 (94) 90014-0.
- Kirkpatrick, David G. (1980), "Una nota sobre Delaunay y triangulaciones óptimas", Information Processing Letters , 10 (3): 127-128, doi : 10.1016 / 0020-0190 (80) 90062-9 , MR 0566856.
- Klincsek, GT (1980), "Triangulaciones mínimas de dominios poligonales", Annals of Discrete Mathematics , 9 : 121-123, doi : 10.1016 / s0167-5060 (08) 70044-x , ISBN 9780444861115.
- Knauer, cristiano; Spillner, Andreas (2006), "Un algoritmo de parámetros fijos para el problema de triangulación de peso mínimo basado en separadores de gráficos pequeños", Conceptos teóricos de gráficos en informática , Lecture Notes in Computer Science, 4271 , Berlín: Springer, págs. 49– 57, doi : 10.1007 / 11917496_5 , MR 2290717.
- Kyoda, Yoshiaki; Imai, Keiko; Takeuchi, Fumihiko; Tajima, Akira (1997), "Un enfoque de ramificación y corte para la triangulación de peso mínimo", Algoritmos y Computación (Singapur, 1997) , Lecture Notes in Computer Science, 1350 , Berlín: Springer, págs. 384–393, doi : 10.1007 / 3-540-63890-3_41 , MR 1651067.
- Lenhart, William; Liotta, Giuseppe (2002), "El problema de dibujabilidad para triangulaciones de peso mínimo", Informática teórica , 270 (1–2): 261–286, doi : 10.1016 / S0304-3975 (00) 00383-2 , MR 1871072.
- Levcopoulos, Christos (1987), "Un límite inferior Ω (√ n ) para la no óptima de la triangulación codiciosa", Information Processing Letters , 25 (4): 247–251, doi : 10.1016 / 0020-0190 (87) 90170- 0 , MR 0896144.
- Levcopoulos, Christos (2008), "Triangulación de peso mínimo", en Kao, Ming-Yang (ed.), Enciclopedia de algoritmos , Springer, págs. 546–548, ISBN 978-0-387-30770-1.
- Levcopoulos, C .; Krznaric, D. (1998), "Triangulaciones cuasi-codiciosas que se aproximan a la triangulación de peso mínimo" (PDF) , Journal of Algorithms , 27 (2): 303–338, doi : 10.1006 / jagm.1997.0918 , MR 1622398.
- Lingas, Andrzej (1986), "Las triangulaciones Greedy y Delaunay no son malas en el caso promedio", Information Processing Letters , 22 (1): 25–31, doi : 10.1016 / 0020-0190 (86) 90038-4.
- Lingas, Andrzej (1987), "Una nueva heurística para la triangulación de peso mínimo", SIAM Journal on Algebraic and Discrete Methods , 8 (4): 646–658, doi : 10.1137 / 0608053 , MR 0918066.
- Lingas, Andrzej (1998), "Algoritmos de tiempo subexponencial para triangulaciones de peso mínimo y problemas relacionados", Actas de la Décima Conferencia Canadiense sobre Geometría Computacional (CCCG'98).
- Lloyd, E. (1977), "Sobre triangulaciones de un conjunto de puntos en el plano", Proc. 18º Simposio del IEEE sobre los fundamentos de la informática , págs. 228–240.
- Manacher, Glenn K .; Zobrist, Albert L. (1979), "Ni la triangulación codiciosa ni la de Delaunay de un conjunto de puntos planos se aproximan a la triangulación óptima", Information Processing Letters , 9 (1): 31-34, doi : 10.1016 / 0020-0190 (79 ) 90104-2 , MR 0537055.
- Meijer, Henk; Rappaport, David (1992), "Cálculo de la triangulación de peso mínimo de un conjunto de puntos ordenados linealmente", Information Processing Letters , 42 (1): 35–38, doi : 10.1016 / 0020-0190 (92) 90129-J , MR 1160443.
- Mulzer, Wolfgang; Rote, Günter (2008), "La triangulación de peso mínimo es NP-hard", Journal of the ACM , 55 (2), Artículo A11, arXiv : cs.CG/0601002 , doi : 10.1145 / 1346330.1346336.
- Plaisted, DA; Hong, J. (1987), "Un algoritmo de triangulación heurística", Journal of Algorithms , 8 (3): 405–437, doi : 10.1016 / 0196-6774 (87) 90020-4.
- Qin, Kaihuai; Wang, Wenping; Gong, Minglun (1997), "Un algoritmo genético para la triangulación de peso mínimo", IEEE International Conference on Evolutionary Computation , págs. 541–546, doi : 10.1109 / ICEC.1997.592370 , hdl : 10722/45578 , Semantic Scholar.
- Remy, Jan; Steger, Angelika (2009), "Un esquema de aproximación de tiempo cuasi-polinomial para la triangulación de peso mínimo", Revista de la ACM , 56 (3), Artículo A15, doi : 10.1145 / 1516512.1516517.
- Shamos, MI ; Hoey, DJ (1975), "Problemas más cercanos", Proc. 16º Simposio del IEEE sobre los fundamentos de la informática (PDF) , págs. 151–162.
- Wang, Cao An; Yang, Boting (2001), "Un límite inferior para β -esqueleto perteneciente a triangulaciones de peso mínimo", Geometría computacional: teoría y aplicaciones , 19 (1): 35–46, doi : 10.1016 / S0925-7721 (01) 00008- 6.
- Xu, Yin-Feng (1998), "Triangulaciones de peso mínimo", Manual de optimización combinatoria, vol. 2 , Boston, MA: Kluwer Academic Publishers, págs. 617–634, MR 1665412.
- Yang, Bo Ting; Xu, Yin Feng; You, Zhao Yong (1994), "Un algoritmo de descomposición en cadena para la prueba de una propiedad en triangulaciones de peso mínimo", en Du, Ding-Zhu; Zhang, Xiang-Sun (eds.), Algorithms and Computation: 5th International Symposium, ISAAC '94, Beijing, PR China, 25 al 27 de agosto de 1994, Actas , Lecture Notes in Computer Science, 834 , Berlín: Springer, págs. 423–427, doi : 10.1007 / 3-540-58325-4_207 , MR 1316441.
enlaces externos
- Triangulación de peso mínimo usando un código fuente LMT Skeleton '