Modelos Matemáticos para o Problema da Poligonização de Área Máxima

Abstract

O problema do caixeiro viajante, do ponto de vista geométrico, tem por objetivo encontrar um polı́gono simples sobre um dado conjunto de vértices cujo perı́metro é mı́nimo. É possı́vel derivar o problema de modo que o objetivo seja encontrar um polı́gono simples cuja área interna seja máxima: trata-se do problema de poligonização de área máxima. Este é um problema de otimização combinatória NP-difı́cil com aplicações práticas em segmentos como reconhecimento de padrões, reconstrução de imagens, clusterização e robótica. Este trabalho apresenta dois modelos matemáticos de programação linear inteira. Experimentos computacionais foram executados para comparar as metodologias propostas com um algoritmo 12 -aproximado da literatura. Os modelos matemáticos propostos mostram a dificuldade de resolver de maneira exata o problema de poligonização de área máxima, encontrando soluções ótimas em uma hora somente para as instâncias de 10 pontos, em um conjunto de instâncias de até 50 pontos.