Triangulación de peso mínimo

Se demostró que este en un problema NP-duro por Mulzer y Rote (2008), mediante una demostración por reducción de grafo plano 1-EN-3, un caso especial del problema de satisfacibilidad booleana en el que un 3-CNF cuyo grafo es planar es aceptado cuándo satisface la condición un literal en cada cláusula.

Aun así, Mulzer y Rote remarcaron que el problema es NP-completo si los pesos de borde son redondeados a valores enteros.

,[3]​ y que la triangulación voraz (aquella formada añadiendo en cada paso el borde más corto posible, mediante la unión del par de vértices más próximos siempre que esta no atraviese un borde anterior) tiene una razón de

[4]​ En cualquier caso, para nubes de puntos distribuidos aleatoriamente, tanto la triangulación de Delaunay como la voraz están dentro del factor logarítmico del peso mínimo.

Sin embargo, es posible una solución cuasi-polinomial: Dada una constante ε > 0, se puede encontrar una solución aproximada con razón 1 + ε en tiempo cuasi-polinomial exp(O((log n)9).