O problema cromático da galeria de arte

• Processo: 13/25104-3
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Mestrado
• Data de Início da vigência: 01 de fevereiro de 2014
• Data de Término da vigência: 30 de abril de 2014
• Á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: Mauricio Jose de Oliveira Zambon
• Supervisor: Sándor P. Fekete
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: 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
• Palavra(s)-Chave do Pesquisador: chromatic art gallery problem | Computational Geometry | Integer Programming | Geometria Computacional

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)