Busca avançada
Ano de início
Entree

O problema cromático da galeria de arte

Processo: 13/25104-3
Linha de fomento:Bolsas no Exterior - Estágio de Pesquisa - Mestrado
Vigência (Início): 01 de fevereiro de 2014
Vigência (Término): 30 de abril de 2014
Á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:Mauricio Jose de Oliveira Zambon
Supervisor no Exterior: Sándor P. Fekete
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Local de pesquisa : University of Technology Braunschweig, Alemanha  
Vinculado à bolsa:12/24993-6 - Soluções exatas para o Problema Cromático da Galeria de Arte, BP.MS
Assunto(s):Geometria computacional   Programação inteira e fluxos em rede

Resumo

Proposto recentemente, o Problema Cromático da Galeria de Arte (Chromatic Art Gallery Problem - CAGP) tem alguns resultados teóricos apresentados na literatura, mas nenhum estudo no que se refere a algoritmos exatos foi realizado até o momento. O CAGP é relacionado ao conhecido Problema da Galeria de Arte (AGP). Contrariamente ao AGP original, nessa variação estamos interessados em minimizar o número de cores usadas em uma coloração válida de um conjunto de guardas que cobre uma dada galeria, representada por um polígono. Uma coloração é válida se quaisquer dois guardas cujos polígonos de visibilidade se intersectam recebem cores diferentes. Não obstante os avanços que nós alcançamos em obter a primeira solução algorítmica para o CAGP à otimalidade, é esperado que a visita científica a Technische Universität Braunschweig melhore os resultados alcançados em duas frentes. Primeiramente, aprimorar nosso método atual para encontrar soluções exatas para o CAGP e, em segundo lugar, fazer progressos em direção a uma prova de NP-dificuldade para o problema. Como um benefício adicional, a colaboração entre os grupos de pesquisa da TUB e UNICAMP será fortalecida. (AU)