Heurísticas para determinação da distância de inversões entre triangulações

• Processo: 15/09789-1
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de agosto de 2015
• Data de Término da vigência: 31 de dezembro de 2016
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Pedro Jussieu de Rezende
• Beneficiário: Yuri Corrêa Pinto Soares
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Geometria computacional Heurística Meta-heurística Triangulação (geometria) Conversores elétricos Otimização combinatória Determinação
• Palavra(s)-Chave do Pesquisador: Brkga | Geometria Computacional | Grasp | heuristicas | Otimização Combinatória | Triangulação | Geometria Computacional

Resumo

Este projeto de iniciação científica visa estudar o problema de determinação da distância de inversões entre triangulações. Dados dois triângulos que compartilham uma aresta numa triangulação e cuja união forma um quadrilátero convexo, uma inversão de aresta consiste em substituir a aresta compartilhada por eles pela outra diagonal do quadrilátero que eles formam. Dadas duas triangulações T1 e T2 de um conjunto de pontos, sabe-se que é possível encontrar um conjunto de inversões de arestas que aplicadas a T1 nos leva a obter T2. O problema de minimização do número de inversões suficientes para se obter T2 a partir de T1 é NP-difícil, mesmo no caso em que T1 e T2 são triangulações de um polígono simples. Esse número é a distância de inversões (de arestas} entre T1 e T2. O desenvolvimento de heurísticas eficientes capazes de obter boas soluções viáveis para esse problema deve permitir resolvê-lo com qualidade superior àquela obtida por algoritmos aproximados. Estudaremos a aplicação das metaheurísticas BRKGA e GRASP ao problema de obtenção de boas e eficientes soluções para a distância de inversões entre triangulações e realizaremos testes estatísticos para medida da qualidade das soluções obtidas e do tempo de execução. Serão consideradas, nesse contexto, triangulações de conjuntos arbitrários de pontos, assim como de polígonos simples e convexos, já que neste último caso a complexidade do problema permanece indeterminada.