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.Vea descripciones del problema en ,, y . 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.
Historia El problema de triangulación de peso mínimo de un conjunto de puntos fue propuesto por , quienes sugirieron su aplicación a la construcción de redes irregulares de triángulos para representar contornos terrestres , proponiendo un algoritmo voráz para aproximarlo. conjeturaron que la triangulación de peso mínimo siempre coincidiría con la triangulación de Delaunay, pero esto fue rápidamente refutado por Lloyd (1977), y de hecho Kirkpatrick (1980) mostró que los pesos de las dos triangulaciones pueden diferir por un factor lineal.See also .
El problema de triangulación de peso mínimo se hizo notorio cuándo lo incluyeron en una lista de problemas abiertos en su libro sobre completitud NP, y muchos autores posteriores publicaron resultados parciales sobre ello. Finalmente, demostró que el problema era NP-duro, y mostró que es posible construir aproximaciones al mismo de forma eficiente.
Complejidad El peso de una triangulación de un conjunto de puntos en el plano euclídeo está definido como la suma de longitudes de sus bordes. Su problema de decisión consiste en decidir si existe alguna triangulación de peso inferior a un peso dado. Se demostró que este en un problema NP-duro por , 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. La demostración empleó ayuda de un ordenador para verificar el comportamiento correcto de la misma.
No es sabido si el problema de triangulación de peso mínimo es NP-completo, ya que este depende del problema aún abierto de determinar si la suma de radicales puede ser computada en tiempo polinómico. Aun así, Mulzer y Rote remarcaron que el problema es NP-completo si los pesos de borde son redondeados a valores enteros.
Cálculo de soluciones aproximadas
Varios autores han relacionado el peso de la triangulación de peso mínimo con el de otras triangulaciones que puedan ser usadas en algún algoritmo de aproximación, calculando el cociente entre ambas. En este sentido, es sabido que la triangulación de Delaunay tiene una razón de ,. Una peor aproximación fue calculada en . 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 .Se publicó una serie de ejemplos demostrando que la razón es en , y el correspondiente límite superior en . Para la razón de aproximación de la triangulación de Delaunay, se había publicado un límite en , que resultó no ser el inferior. 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..
El trabajo de Mulzer y Rote también implica la complejidad NP-Hard de encontrar una solución aproximada que asegure un error inferior a O(1/n2), así que es poco probable que pueda encontrarse un algoritmo que calcule la triangulación de peso mínimo en tiempo polinómico. 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).Vea . Para resultados anteriores en tiempo polinomial, vea (log-factor approximation) y (constant-factor approximation).
Referencias
. . . . . . . . . . . . As cited by and . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Enlaces externos Minimum Weight Triangulation using an LMT Skeleton source code'
Categoría:Algoritmos geométricos Peso mínimo Categoría:Pruebas asistidas por ordenador Categoría:Triangulación (geometría) Categoría:Problemas NP-difíciles