Triangulación de peso mínimo

Triangulación de puntos que minimiza la longitud total

Tres posibles triangulaciones del mismo polígono. La triangulación central tiene menor peso (suma de perímetros).

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 con una longitud de arista total mínima . ^[1] Es decir, un polígono de entrada o la envoltura convexa de un conjunto de puntos de entrada debe subdividirse en triángulos que se encuentren de arista a arista 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 entradas de conjuntos de puntos, pero se puede aproximar a cualquier grado deseado de precisión. Para entradas de polígonos, se puede resolver exactamente en tiempo polinomial. La triangulación de peso mínimo también se ha denominado a veces triangulación óptima .

Historia

El problema de la triangulación de peso mínimo de un conjunto de puntos fue planteado por Düppe y 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 voraz 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) demostró que los pesos de las dos triangulaciones pueden diferir en un factor lineal. ^[2]

El problema de triangulación de peso mínimo se hizo famoso 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-hard, y Remy y Steger (2009) demostraron que se pueden construir aproximaciones precisas al problema de manera eficiente.

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 aristas. Su variante de decisión es el problema de decidir si existe una triangulación de peso menor que un peso dado; Mulzer y Rote (2008) demostraron que es NP-hard . Su prueba es por reducción de PLANAR-1-IN-3-SAT, un caso especial del problema de satisfacibilidad booleano en el que se acepta una 3-CNF cuyo gráfico es planar cuando tiene una asignación de verdad que satisface exactamente un literal en cada cláusula . La prueba utiliza dispositivos complejos e implica la asistencia de una computadora 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 señalan que el problema es NP-completo si los pesos de las aristas se redondean a valores enteros.

Aunque es NP-hard, la triangulación de peso mínimo se puede construir en tiempo subexponencial mediante un algoritmo de programación dinámica que considera todos los posibles separadores de ciclos simples de puntos 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] ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle 2^{O({\sqrt {n}}\log n)}}$

Aproximación

Varios autores han demostrado resultados que relacionan la triangulación de peso mínimo con otras triangulaciones en términos de la razón de aproximación , la razón en el peor de los casos de la longitud total de la arista de la triangulación alternativa a la longitud total de la triangulación de peso mínimo. En esta línea, se sabe que la triangulación de Delaunay tiene una razón de aproximación de , ^[4] y que la triangulación voraz (la triangulación formada añadiendo aristas en orden de la más corta a la más larga, incluyendo en cada paso una arista siempre que no cruce una arista anterior) tiene una razón de aproximación de . ^[5] Sin embargo, para conjuntos de puntos distribuidos aleatoriamente, tanto la triangulación de Delaunay como la voraz están dentro de un factor logarítmico del peso mínimo. ^[6] ${\displaystyle \Theta (n)}$ ${\displaystyle \Theta ({\sqrt {n}})}$

El resultado de dureza de Mulzer y Rote también implica la NP-dureza de encontrar una solución aproximada con un error de aproximación relativo de como máximo O(1/n ² ). Por lo tanto, es poco probable que exista 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 razón de aproximación 1 + ε en un tiempo cuasi-polinomial exp(O((log  n ) ⁹ ). ^[7]

Heurística

Debido a la dificultad de encontrar las soluciones exactas de la triangulación de peso mínimo, muchos autores han estudiado heurísticas que pueden en algunos casos encontrar la solución, aunque no se puede demostrar 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 se garantice que pertenecen a la triangulación de peso mínimo. Si un subgrafo de la triangulación de peso mínimo encontrado de esta manera resulta ser conexo, entonces el espacio no triangulado restante puede verse como formando un polígono simple, y la triangulación completa puede encontrarse utilizando programación dinámica para encontrar la triangulación óptima de este espacio poligonal. El mismo enfoque de programación dinámica también puede extenderse al caso en que el subgrafo tenga un número acotado de componentes conexos ^[8] y el mismo enfoque de encontrar un grafo conexo y luego aplicar programación dinámica para llenar los huecos poligonales que rodean las aristas del grafo también se ha utilizado como parte de la heurística para encontrar triangulaciones de bajo peso pero no de peso mínimo. ^[9]

El grafo formado al conectar dos puntos siempre que sean vecinos más cercanos entre sí es necesariamente un subgrafo de la triangulación de peso mínimo. ^[10] Sin embargo, este grafo de vecino más cercano mutuo es un coincidente y, por lo tanto, nunca está conectado. Una línea de investigación relacionada encuentra grandes subgrafos de la triangulación de peso mínimo mediante el uso de β -esqueletos basados ​​en círculos , los grafos geométricos formados al incluir una arista 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 grafo formado de esta manera es un subgrafo de la triangulación de peso mínimo. ^[11] Sin embargo, la elección de θ necesaria para garantizar 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 denominada esqueleto LMT. Se forma mediante un proceso iterativo en el que se mantienen dos conjuntos de aristas: un conjunto de aristas que se sabe que 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 aristas conocidas se inicializa en la envoltura convexa de la entrada y todos los pares de vértices restantes forman aristas candidatas. Luego, en cada iteración del proceso de construcción, las aristas candidatas se eliminan siempre que no haya un par de triángulos formados por las aristas restantes que formen un cuadrilátero para el que la arista candidata sea la diagonal más corta, y las aristas candidatas se mueven al conjunto de aristas conocidas cuando no hay otra arista candidata que las cruce. El esqueleto LMT se define como el conjunto de aristas conocidas que se produce 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 con 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], branch and bound [ ^15] y algoritmos de optimización de colonias de hormigas ^[16] .

Variaciones

Se puede construir una triangulación de polígonos de peso mínimo en tiempo cúbico utilizando el enfoque de programación dinámica , informado independientemente 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 hasta el 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 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:
  • Para cada valor posible de j , desde i  + 1 hasta n , 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 )

Una vez que se completa esta iteración, MWT(1, n ) almacenará el peso total de la triangulación de peso mínimo. La triangulación en sí se puede obtener buscando recursivamente en esta matriz, comenzando desde MWT(1, n ), eligiendo en cada paso el triángulo ijk que conduce al valor mínimo para MWT( i , j ) y buscando recursivamente MWT( i , k ) y MWT( j , k ).

También se pueden adaptar métodos de programación dinámica similares a entradas de conjuntos de puntos donde todos los puntos, excepto un número constante, se encuentran en la envoltura convexa de la entrada, ^[17] y a conjuntos de puntos que se encuentran en un número constante de polígonos convexos anidados o en un número constante de líneas, ninguna de las cuales se cruza dentro de la envoltura convexa. ^[18]

También es posible formular una versión de los problemas de triangulación de polígonos o conjuntos de puntos en los que se permite añadir puntos de Steiner , vértices adicionales, para reducir la longitud total de las aristas 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]

Problemas relacionados que también se han estudiado incluyen la construcción de pseudotriangulaciones de peso mínimo ^[20] y la caracterización de los gráficos de triangulaciones de peso mínimo. ^[21]

Notas

1. Para estudios sobre el problema, véase Xu (1998), Levcopoulos (2008) y De Loera, Rambau & Santos (2010).
2. Véase también Manacher y Zobrist (1979).
3. Lingas (1998).
4. Kirkpatrick (1980). Manacher y Zobrist (1979) dieron un límite más débil.
5. Levcopoulos (1987) proporcionó una familia de ejemplos que demuestran que la razón de aproximación es , y el límite superior correspondiente es de Levcopoulos y Krznaric (1998). Al igual que con la razón de aproximación para la triangulación de Delaunay, Manacher y Zobrist (1979) también proporcionaron un límite más débil. ${\displaystyle \Omega ({\sqrt {n}})}$
6. Lingas (1986).
7. Remy y Steger (2009). Para consultar resultados anteriores sobre algoritmos de aproximación en tiempo polinomial, véase Plaisted y Hong (1987) (aproximación de factor logarítmico) y Levcopoulos y Krznaric (1998) (aproximación de factor constante).
8. Cheng, Golin y Tsang (1995).
9. Lingas (1987); Salud y Pemmaraju (1994).
10. Yang, Xu y You (1994).
11. Keil (1994); Cheng, Golin y Tsang (1995); Cheng y Xu (2001); Hu (2010).
12. Dickerson y Montague (1996); Cheng, Katoh y Sugai (1996); Beirouti y Snoeyink (1998); Aichholzer, Aurenhammer y Hainz (1999).
13. Bose, Devroye y Evans (1996).
14. Qin, Wang y Gong (1997); Capp y Julstrom (1998).
15. Kyoda y otros (1997).
16. Jahani, Bigham y Askari (2010).
17. Hoffmann y Okamoto (2004); Grantson, Borgelt y Levcopoulos (2005); Knauer y Spillner (2006).
18. Anagnostou y Corneil (1993); Meijer y Rappaport (1992).
19. Eppstein (1994).
20. Gudmundsson y Levcopoulos (2007); Aichholzer et al. (2009).
21. Lenhart y Liotta (2002).

Referencias

• Aichholzer, Oswin; Aurenhammer, Franz ; Hackl, Thomas; Speckmann, Bettina (2009), "Sobre pseudo-triangulaciones de peso mínimo", Computational Geometry Theory and Applications , 42 (6–7): 627–631, doi : 10.1016/j.comgeo.2008.10.002 , MR  2519380.
• Aichholzer, Oswin; Aurenhammer, Franz ; Hainz, Reinhard (1999), "Nuevos resultados sobre subgrafos MWT", Information Processing Letters , 69 (5): 215–219, doi :10.1016/S0020-0190(99)00018-6.
• Anagnostou, Efthymios; Corneil, Derek (1993), "Instancias de tiempo polinomial del problema de triangulación de peso mínimo", Computational Geometry. Theory and Applications , 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 ACM sobre geometría computacional , págs. 96-105, doi : 10.1145/276884.276895 , S2CID  15102126.
• Bose, Prosenjit ; Devroye, Luc; Evans, William (1996), "Los diamantes no son el mejor amigo de una triangulación de peso mínimo", Proc. 8.ª Conferencia Canadiense sobre Geometría Computacional (CCCG 1996) (PDF) , págs. 68–73.
• Capp, Kerry; Julstrom, Bryant A. (1998), "Un algoritmo genético con código de peso para el problema de triangulación de peso mínimo", Proc. ACM Symposium on Applied Computing , Atlanta, Georgia, Estados Unidos, págs. 327–331, doi :10.1145/330560.330833, S2CID  13589205, Semantic Scholar{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).
• 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. 7th Canadian Conference on Computational Geometry (CCCG 1995) , págs. 279–284.
• Cheng, Siu-Wing; Katoh, Naoki; Sugai, Manabu (1996), "Un estudio del esqueleto LMT", Algorithms and Computation , Lecture Notes in Computer Science, vol. 1178, págs. 256-265, doi :10.1007/BFb0009502, ISBN 978-3-540-62048-8.
• Cheng, Siu-Wing; Xu, Yin-Feng (2001), "Sobre el β -esqueleto como subgrafo de la triangulación de peso mínimo", 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 voraces y de peso mínimo", Triangulaciones: Estructuras para algoritmos y aplicaciones , Algorithms and Computation in Mathematics, vol. 25, Springer, pp. 102–107, ISBN 978-3-642-12970-4.
• Dickerson, Matthew T .; Montague, Mark H. (1996), "Un subgrafo (¿generalmente?) conectado de la triangulación de peso mínimo", Proc. 12.º Simposio ACM sobre geometría computacional , págs. 204-213, doi :10.1145/237218.237364, S2CID  18962760.
• Duppe, RD; Gottschalk, HJ (1970), "Automatische Interpolation von Isolinien bei willkürlich verteilten Stützpunkten", Allgemeine Vermessungs-Nachrichten , 77 : 423–426Como citan Mulzer y Rote (2008) y Remy y Steger (2009).
• Eppstein, David (1994), "Aproximación de la triangulación de Steiner con peso mínimo" (PDF) , Geometría discreta y computacional , 11 (2): 163–191, doi : 10.1007/BF02574002 , MR  1254088.
• Garey, MR ; Johnson, DS (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , San Francisco, California: WH Freeman, Problema OPEN12, pág. 288, ISBN 0-7167-1045-5, Sr.  0519066.
• Gilbert, PD (1979), Nuevos resultados en triangulaciones planares , Informe R-850, Urbana, Illinois: Laboratorio de Ciencias Coordinadas, Universidad de Illinois.
• Grantson, M.; Borgelt, C.; Levcopoulos, C. (2005), "Triangulación de peso mínimo mediante el recorte de triángulos", Proc. 16.° Simposio Internacional sobre Algoritmos y Computación , págs. 984–994.
• Gudmundsson, Joachim; Levcopoulos, Christos (2007), "Pseudotriangulaciones de peso mínimo", Computational Geometry Theory and Applications , 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, hdl : 10919/19701 , MR  1297812, S2CID  21160664.
• Hoffmann, M.; Okamoto, Y. (2004), "El problema de triangulación de peso mínimo con pocos puntos internos", Proc. 1er Taller Internacional sobre Cálculo Parametrizado y Exacto , pp. 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, S2CID  869128.
• 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, S2CID  11790811, Semantic Scholar.
• Keil, J. Mark (1994), "Cálculo de un subgrafo de la triangulación de peso mínimo", Computational Geometry: Theory & Applications , 4 (1): 18–26, doi : 10.1016/0925-7721(94)90014-0.
• Kirkpatrick, David G. (1980), "Una nota sobre Delaunay y las 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, Christian; Spillner, Andreas (2006), "Un algoritmo de parámetros fijos para el problema de triangulación de peso mínimo basado en separadores de grafos pequeños", Graph-Theoretic Concepts in Computer Science , Lecture Notes in Computer Science, vol. 4271, Berlín: Springer, págs. 49–57, doi :10.1007/11917496_5, ISBN 978-3-540-48381-6, Sr.  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", Algorithms and Computation (Singapur, 1997) , Lecture Notes in Computer Science, vol. 1350, Berlín: Springer, págs. 384–393, doi :10.1007/3-540-63890-3_41, ISBN 978-3-540-63890-2, Sr.  1651067.
• Lenhart, William; Liotta, Giuseppe (2002), "El problema de dibujabilidad para triangulaciones de peso mínimo", Theoretical Computer Science , 270 (1–2): 261–286, doi :10.1016/S0304-3975(00)00383-2, MR  1871072.
• Levcopoulos, Christos (1987), "Un límite inferior de Ω(√ n ) para la no optimalidad de la triangulación voraz", 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-voraces 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, S2CID  13991653.
• Lingas, Andrzej (1986), "Las triangulaciones de 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 10.ª Conferencia canadiense sobre geometría computacional (CCCG'98).
• Lloyd, E. (1977), "Sobre triangulaciones de un conjunto de puntos en el plano", Actas del 18.º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación , págs. 228-240.
• Manacher, Glenn K.; Zobrist, Albert L. (1979), "Ni la triangulación voraz 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, S2CID  1658062.
• 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 , S2CID  18775737, Semantic Scholar.
• Remy, Jan; Steger, Angelika (2009), "Un esquema de aproximación temporal cuasi-polinomial para la triangulación de peso mínimo", Journal of the ACM , 56 (3), Artículo A15, doi :10.1145/1516512.1516517, S2CID  1781658.
• Shamos, MI ; Hoey, DJ (1975), "Problemas de punto más cercano", Actas del 16.º Simposio IEEE sobre Fundamentos de la Ciencia de la Computación (PDF) , págs. 151-162.
• Wang, Cao An; Yang, Boting (2001), "Un límite inferior para el β -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", Handbook of Combinatorial Optimization, 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.), Algoritmos y computación: 5.º simposio internacional, ISAAC '94, Pekín, República Popular China, 25-27 de agosto de 1994, Actas , Lecture Notes in Computer Science, vol. 834, Berlín: Springer, págs. 423-427, doi :10.1007/3-540-58325-4_207, ISBN 978-3-540-58325-7, Sr.  1316441.

Enlaces externos

• Triangulación de peso mínimo utilizando un código fuente de esqueleto LMT