Introducción
El objetivo de este proyecto es de desarrollar una aplicación software en Java para mostrar gráficamente el resultado de aplicar estrategias de programación dinámica para calcular triangulaciones de peso mínimo en nubes de puntos y polígonos.

Una triangulación de un conjunto de puntos es un conjunto finito de aristas, trazadas en el espacio, de forma que se trace el mayor número de aristas posibles sin que se crucen entre sí. Esa propiedad implica en que todas las caras (faces) del grafo sean un triángulo (Tan, 1993). En otras palabras, dado un conjunto S de puntos en el plano, una triangulación de S es un grafo geométrico maximal sin cortes sobre S.
El peso de una triangulación es la suma de los pesos de todas sus aristas, donde normalmente (y en este proyecto), se trata de la distancia euclidea entre sus dos vértices (Loera, 2009).
Existen diversos algoritmos para obtener triangulaciones de un conjunto de puntos, donde cada uno explora, maximiza o minimiza alguna característica especial de la triangulación. Por ejemplo, maximizar el ángulo más pequeño de todos los triángulos resultantes (algoritmo de Delaunay).
Una triangulación de peso mínimo (MWT) es aquella donde la suma de los pesos de sus aristas es la mínima posible. Si se quiere minimizar la longitud de la máxima arista de una triangulación, entonces obtenemos una triangulación MLT (Tan, 1993).
Debido a que el cálculo de la MWT es un problema NP-Duro (Loera, 2009), se puede dividir la triangulación en pequeñas piezas independientes, y aplicar, sobre cada pieza, un algoritmo que resuelva el problema (esta estrategia se llama “programación dinámica”).
En este proyecto, estudiaremos distintas estrategias de programación dinámica para obtener el resultado exacto y/o una aproximación de las triangulaciones MWT para cualquier nube de puntos.
Los resultados obtenidos a través de la descomposición de la nube en piezas menores y posterior aplicación de algoritmos polinómicos para MWT, nos devuelve una aproximación a la triangulación de peso mínimo. No obstante, obtenemos el resultado exacto de la triangulación MLT, por tratarse de un problema polinómico.