Busca avançada
Ano de início
Entree

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

Processo: 15/09789-1
Linha de fomento:Bolsas no Brasil - Iniciação Científica
Vigência (Início): 01 de agosto de 2015
Vigência (Término): 31 de dezembro de 2016
Área do 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

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.