Triangulación de peso mínimo
De Wikipedia, la enciclopedia encyclopedia
En geometría computacional, se denomina problema de triangulación de peso mínimo (Minimum-weight triangulation o MWT) al problema de encontrar una triangulación de longitud de borde total mínima.[1] Es decir, dado un polígono de entrada (o el cierre convexo de un conjunto de puntos de la entrada) encontrar la subdivisión del mismo en triángulos adyacentes, de tal manera que se minimice la suma de los perímetros de los triángulos. El problema es NP-duro para entradas consistentes en conjuntos de puntos, pero puede ser aproximado con cualquier grado deseado de exactitud. Si la entrada consiste en un polígono, puede ser solucionado exactamente en tiempo polinómico. La triangulación de peso mínimo también se ha denominado a veces la triangulación óptima.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Convex_Polygon_triangulations.svg/640px-Convex_Polygon_triangulations.svg.png)