Uma Abordagem de Programação Inteira para o Problema da Triangulação de Custo Mínimo

Dado um conjunto finito de pontos no plano, uma triangulação planar é definida como um conjunto maximal de segmentos de reta conectando estes pontos, tal que dois destes segmentos não se interceptam, exceto nos extremos. Chamamos de triangulação de custo mínimo a triangulação planar cuja soma total dos comprimentos de seus segmentos de reta é mínimo dentre todas as triangulações planares do conjunto de pontos em questão. \par Não se conhece algoritmo polinomial que resolva o problema de determinar a triangulação de custo mínimo de um conjunto de pontos no caso geral, contudo, também não está provado tratar-se de um problema {NP}-difícil. \par Neste artigo estamos interessados na resolução exata deste problema. Nossa abordagem é baseada em técnicas de programação inteira, em particular avaliamos duas formulações distintas para o problema. \par A primeira formulação é baseada em uma equivalência entre o problema da triangulação de custo mínimo e uma versão restrita do problema do conjunto independente em um grafo. Além das desigualdades obtidas através da observação desta equivalência, mostramos como fortalecer a formulação através de certas propriedades geométricas do problema. \par Avaliamos ainda uma outra formulação baseada principalmente no trabalho apresentado por Loera {\em et. al} em {\em The Polytope of All Triangulations of a Point Configuration}, 12th European Workshop on Computational Geometry, 1996. Finalmente, reportamos nossos experimentos computacionais.

1996