Triangulação de Custo Mínimo

Considere n pontos em posição geral no plano. Considere todos os segmentos de reta que unem dois desses pontos quaisquer e com um custo associado. Uma triangulação desses pontos é um subconjunto maximal desses segmentos tal que dois segmentos nesse subconjunto não se interceptem (exceto nas pontas). O problema da triangulação de custo mínimo consiste em encontrar uma triangulação que minimize a soma dos custos dos segmentos. Existe uma variante muito famosa  em geometria computacional, onde a função objetivo é maximizar o menor ângulo entre dois lados de algum triângulo da triangulação, conhecida também como triangulação de Delaunay .

Exemplo de triangulação

Recentemente (2008) foi provado que esse problema é NP-difícil [1]. Entretanto, encontrei um artigo de 1997 que apresenta um modelo de PLI para esse problema [2]. Estou tentando uma abordagem parecida na minha tese, ou seja, atacando um problema cuja pertinência a classe NPC é um problema em aberto. Enfim, vamos ao modelo.

Modelo

Começamos com um teorema:
O número de segmentos em uma triangulação com n pontos é:

Além do mais, considere o grafo Gs, onde cada vértice corresponde a um segmento e existe uma aresta ligando dois vértices se seus segmentos correspondentes se interceptam. É possível mostrar que conjuntos independentes maximais nesse tipo de grafo têm uma correspondência um pra um com triangulações, ou seja queremos um conjunto independente de tamanho .

Como os segmentos têm custo associado (geralmente dado pela distância euclidiana), associamos esses mesmos custos aos vértices. Desta forma, seja o custo de cada vértice v. Definimos a variável se o vértice está no conjunto independente e 0 caso contrário.

O modelo fica:

(1)

(2)

(3)

A desigualdade (2) impede que dois vértices adjacentes estejam em no conjunto independente. A desigualdade (3) garante que o conjunto independente é maximal.

Trabalhei com o Pedro Hokama em cima desse problema no trabalho 2 da disciplina de Programação linear inteira. Consideramos algumas desigualdades adicionais para fortalecer o modelo e que estão presentes em [2,3], além de usar alguma delas como cortes para o algoritmo de Branch and Cut. Um relatório deste trabalho pode ser encontrado aqui.

Referências:

[1] Mulzer, W. and Rote, G. – Minimum-weight triangulation is NP-hard (http://arxiv.org/abs/cs.CG/0601002)
[2] Yoda, Y. and Imai, K. and Takeuchi, F. and Tajima, A. – A branch-and-cut approach for minimum weight triangulation
[3] Nemhauser, G.L. and Sigismondi, G.A – Strong cutting plane/branch-and-bound algorithm for node packing

Os comentários estão fechados.

%d bloggers like this: