Hispanopedia Wiki
Articulo de referencia

Triangulación de peso mínimo

Tres posibles triangulaciones del mismo polígono. La triangulación central tiene menor peso (suma de perímetros). En geometría computacional e informática , el problema de trian...

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

En geometría computacional e informática , el problema de triangulación de peso mínimo consiste en encontrar una triangulación con una longitud total de arista 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 unan arista con arista y vértice con vértice, de 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 puede aproximarse con cualquier grado de precisión deseado. Para entradas de polígonos, puede resolverse 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 de terrenos, 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 por un factor lineal. [ 2 ]

El problema de la 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-difícil, y Remy y Steger (2009) demostraron que se pueden construir aproximaciones precisas 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 determinar si existe una triangulación con un peso menor que un peso dado; Mulzer y Rote (2008) demostraron que es NP-difícil . Su demostración se basa en la reducción de PLANAR-1-IN-3-SAT, un caso especial del problema de satisfacibilidad booleana en el que se acepta una 3-CNF cuyo grafo es planar cuando tiene una asignación de verdad que satisface exactamente un literal en cada cláusula . La demostración utiliza dispositivos complejos y requiere asistencia informática para verificar el correcto funcionamiento de estos dispositivos.

Se desconoce 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 NP-difícil, 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 ciclo simples de puntos dentro de la triangulación, encuentra recursivamente la triangulación óptima a cada lado del ciclo y elige el separador de ciclo que produce el menor peso total. El tiempo total para este método es . [ 3 ]O(norte){\displaystyle O({\sqrt {n}})}2O(norteregistro⁡norte){\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 caso de la longitud total de las aristas de la triangulación alternativa con 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 voraz (la triangulación formada al agregar 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 se encuentran dentro de un factor logarítmico del peso mínimo. [ 6 ]Θ(norte){\displaystyle \Theta (n)}Θ(norte){\displaystyle \Theta ({\sqrt {n}})}

El resultado de dificultad de Mulzer y Rote también implica la NP-dificultad de encontrar una solución aproximada con un error de aproximación relativo como máximo O(1/n² ) . Por lo tanto, es improbable un esquema de aproximación totalmente polinomial para la triangulación de peso mínimo. Sin embargo, es posible un esquema de aproximación cuasipolinomial: para cualquier constante ε₀, se puede encontrar una solución con una razón de aproximación de 1 + ε en un tiempo cuasipolinomial exp(O(log  n ) ₉ ). [ 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 hallar la solución, aunque no se puede demostrar su eficacia en todos los casos. En particular, gran parte de esta investigación se ha centrado en el problema de encontrar conjuntos de aristas que garanticen pertenecer a la triangulación de peso mínimo. Si un subgrafo de la triangulación de peso mínimo hallado de esta manera resulta ser conexo, el espacio restante no triangulado puede considerarse como un polígono simple , y la triangulación completa puede hallarse mediante 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 limitado de componentes conexas [ 8 ] , y el mismo enfoque de encontrar un grafo conexo y luego aplicar programación dinámica para rellenar los huecos poligonales que rodean las aristas del grafo también se ha utilizado como parte de heurísticas 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 vecinos más cercanos mutuos es un emparejamiento y, por lo tanto, nunca está conectado. Una línea de investigación relacionada encuentra subgrafos grandes de la triangulación de peso mínimo utilizando β- 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 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 . Esta 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 con 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 cuando no hay ningún par de triángulos formados por las aristas restantes que formen un cuadrilátero para el cual 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 producido después de que este proceso deja de realizar más cambios. Se garantiza que sea 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ó frecuentemente. [ 12 ] Sin embargo, se ha demostrado que en promedio para conjuntos de puntos grandes tiene un número lineal de componentes conexas. [ 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 acotación [ 15 ] y algoritmos de optimización de colonias de hormigas [ 16 ] .

Variaciones

Se puede construir una triangulación de polígono de peso mínimo en tiempo cúbico utilizando el enfoque de programación dinámica , reportado 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, se calcula la triangulación óptima 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 de la arista 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 , desde i  + 1 hasta n , haga lo siguiente:
      • Si ij es un borde del polígono, establezca MWT( i , j ) = longitud( 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 completada 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 este array, 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 ).

Métodos de programación dinámica similares también pueden adaptarse a conjuntos de puntos de entrada 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 de las cuales ninguna se cruza dentro de la envoltura convexa. [ 18 ]

También es posible formular una versión de los problemas de triangulación de conjuntos de puntos o polígonos en la 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 por un factor lineal. Es posible aproximar la triangulación de Steiner de peso mínimo de un conjunto de puntos con una precisión de un factor constante respecto al óptimo, pero dicho factor constante en la aproximación es grande. [ 19 ]

Entre los problemas relacionados que también se han estudiado se incluyen la construcción de pseudotriangulaciones de peso mínimo [ 20 ] y la caracterización de los grafos de triangulaciones de peso mínimo. [ 21 ]

Notas

  1. ↑ Para estudios sobre el problema, véanse 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 una cota más débil.
  5. Una familia de ejemplos que prueba que la razón de aproximación esfue dada por Levcopoulos (1987) , y la cota superior correspondiente es por 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 dieron una cota más débil.Ω(norte){\displaystyle \Omega ({\sqrt {n}})}
  6. ^ Lingas (1986) .
  7. ^ Remy y Steger (2009) . Para resultados anteriores sobre algoritmos de aproximación en tiempo polinomial, véanse Plaisted y Hong (1987) (aproximación por factor logarítmico) y Levcopoulos y Krznaric (1998) (aproximación por factor constante).
  8. ^ Cheng, Golin y Tsang (1995) .
  9. ^ Lingas (1987) ; Salud y Pemmaraju (1994) .
  10. ^ Yang, Xu y tú (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 et al. (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 pseudotriangulaciones 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), "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", 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 triangulación de peso mínimo", Actas del 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", Actas de la 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 codificación de peso para el problema de triangulación de peso mínimo", Actas del Simposio ACM sobre Computación Aplicada , Atlanta, Georgia, Estados Unidos, pp.  327–331 , doi : 10.1145/330560.330833 , S2CID  13589205 , Semantic Scholar{{citation}}: CS1 mantenimiento: falta el editor de ubicación ( 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", Actas de la 7.ª 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", Algorithms and Computation , Lecture Notes in Computer Science, vol. 1178, pp.  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 , Algoritmos y computación en matemáticas, 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", Actas del 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– 426. Como citan Mulzer y Rote (2008) y Remy y 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 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", Actas del 16.º Simposio Internacional sobre Algoritmos y Computación , págs.  984–994.
  • Gudmundsson, Joachim; Levcopoulos, Christos (2007), "Pseudotriangulaciones 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 , 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", Actas del 1er Taller Internacional sobre Computación Parametrizada y Exacta , págs.  200–212.
  • Hu, Shiyan (2010), "Una nueva región de inclusión asimétrica para 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) , pp.  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" , 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{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace ).
  • Knauer, Christian; Spillner, Andreas (2006), "Un algoritmo de parámetros fijos para el problema de triangulación de peso mínimo basado en pequeños separadores de grafos", Graph-Theoretic Concepts in Computer Science , Lecture Notes in Computer Science, vol. 4271, Berlín: Springer, pp.  49–57 , doi : 10.1007/11917496_5 , ISBN 978-3-540-48381-6, 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", Algorithms and Computation (Singapur, 1997) , Lecture Notes in Computer Science, vol. 1350, Berlín: Springer, pp.  384–393 , doi : 10.1007/3-540-63890-3_41 , ISBN 978-3-540-63890-2, MR  1651067.
  • Lenhart, William; Liotta, Giuseppe (2002), "El problema de la 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 Ω(√ 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, pp.  546–548 , ISBN 978-0-387-30770-1.
  • Levcopoulos, C.; Krznaric, D. (1998), "Triangulaciones cuasi-voraces que aproximan 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 Informática , 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-difícil", 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", Conferencia Internacional IEEE sobre Computación Evolutiva , pp.  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 de tiempo cuasipolinomial para 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 del punto más cercano", Actas del 16.º Simposio IEEE sobre Fundamentos de la Informática (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", 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.), 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, pp.  423-427 , doi : 10.1007/3-540-58325-4_207 , ISBN 978-3-540-58325-7, MR  1316441.
  • Triangulación de peso mínimo utilizando un código fuente de esqueleto LMT
Obtenido de " https://en.wikipedia.org/w/index.php?title=Minimum-weight_triangulation&oldid=1323428697 "