Triangularização de Peso Mínimo

Uma triangularização de um conjunto de pontos consiste em encontrarmos arestas que conectam estes pontos de tal modo que nenhuma delas cruze com nenhuma outra e cada ponto seja vértice de pelo menos um triangulo formado por essas aresta. Essas arestas particionam o conjunto de pontos em triângulos, daí o nome Triangularização.

A Triangularização de Peso Mínimo é mais um caso particular de triangularização. O que a diferencia é a propriedade de que a soma dos comprimentos das arestas que formam a triangularização é mínima, ou seja, dada esta triangularização, que chamaremos de MWT (Minimum Weight Triangulation), não conseguimos encontrar nenhuma outra triangularização com peso menor.

Se o problema for restrito a triangularizarmos um polígono, existe um algoritmo exato que utiliza programação dinâmica (algoritmo de Gilbert) e é executado com complexidade de tempo O(n³). A idéia do algoritmo é a de que a solução ótima depende da subsolução ótima para um subpolígono do polígono original acrescentando-se uma aresta. Então reduz-se o problema ao máximo (polígonos com apenas 1 vértice) e em seguida resolvemos os subproblemas crescentemente até alcançarmos a solução para o problema original.

O problema para um conjunto de pontos permanece em aberto. Até hoje não se conseguiu um algoritmo polinomial que resolva o problema, nem se conseguiu provar que ele seja NP-completo. Daí o porque de muitos pesquisadores em Ciência da Computação estarem interessados neste problema.Porém, existem muitos algoritmos que utilizam heurísticas que produzem respostas aproximadas da solução ótima. Portanto, este é um problema importante na área de Otimização Combinatória.

A Triangularização Gulosa usa um algoritmo guloso para calcular a Triangularização de Peso Mínimo. Este algoritmo é composto de dois passos: o primeiro é determinar e ordenar crescentemente todos os possíveis segmentos de reta no conjunto de pontos dado. O segundo passo é escolher sempre o menor segmento do conjunto previamente ordenado que não cruze com nenhum outro segmento já escolhido. O algoritmo produz uma triangularização que se aproxima da triangularização de peso mínimo. Um exemplo do resultado do algoritmo para um conjunto de 10 pontos pode ser visto na figura.

Uma outra idéia é a de se achar uma árvore geradora do grafo planar representado pelo conjunto de pontos dado que contenha o fecho convexo do conjunto exceto por uma aresta. Conectando essa árvore a essa aresta descartada do fecho convexo teríamos um polígono degenerado, denominado célula. Cada aresta da árvore seria duas arestas da célula (ida e volta) e cada aresta do fecho seria uma aresta da célula. Aplicando-se o Algoritmo de Gilbert para triangularização de peso mínimo de polígonos à célula (que é um polígono degenerado) resolvemos o problema de forma ótima. O problema então fica reduzido a encontrarmos a árvore ótima.

Desse modo, a maior parte das heurísticas desenvolvidas para este problema ataca esse lado do problema e tenta achar uma árvore tão próxima da árvore ótima quanto possível. Uma idéia seria utilizar a árvore espalhada mínima que contém os menores segmentos que formam uma árvore no conjunto. Mas existe um contra-exemplo que mostra que a aplicação da idéia não produz a solução ótima.