Triangulación de peso mínimo

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.

Tres posibles triangulaciones de un polígono. 1. Abanico. 2. Mínimo peso(suma de perímetros) 3. Delaunay

Historia

editar

El problema de triangulación de peso mínimo de un conjunto de puntos fue propuesto por Düppe y Gottschalk (1970) , 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.Shamos y Hoey (1975) 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.[2]

El problema de triangulación de peso mínimo se hizo notorio cuándo Garey y Johnson (1979) lo incluyeron en una lista de problemas abiertos en su libro sobre completitud NP, y muchos autores posteriores publicaron resultados parciales sobre ello. Finalmente,Mulzer y Rote (2008) demostró que el problema era NP-duro, y Remy y Steger (2009) mostró que es posible construir aproximaciones al mismo de forma eficiente.

Complejidad

editar

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 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. 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

editar
 
La triangulación voraz de un polígono no siempre coincide con la triangulación de peso mínimo, pero es una aproximación calculada en tiempo aceptable.

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  ,[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.[5]

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).[6]

Referencias

editar
  1. Vea descripciones del problema en Xu (1998),Levcopoulos (2008), y De Loera, Rambau y Santos (2010).
  2. See also Manacher y Zobrist (1979).
  3. Kirkpatrick (1980). Una peor aproximación fue calculada en Manacher y Zobrist (1979).
  4. Se publicó una serie de ejemplos demostrando que la razón es   en Levcopoulos (1987), y el correspondiente límite superior en Levcopoulos y Krznaric (1998). Para la razón de aproximación de la triangulación de Delaunay, se había publicado un límite en Manacher y Zobrist (1979), que resultó no ser el inferior.
  5. Lingas (1986).
  6. Vea Remy y Steger (2009). Para resultados anteriores en tiempo polinomial, vea Plaisted y Hong (1987) (log-factor approximation) y Levcopoulos y Krznaric (1998) (constant-factor approximation).

Enlaces externos

editar