============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Um algoritmo exato  para um problema de galeria 
             de arte

Palestrante: Pedro Jussieu de Rezende
             Instituto de Computação
             Universidade de Campinas

Hora e Data: 14h, sexta-feira, 05 de novembro de 2010

Local:       auditório do NUMEC

Resumo:

Sabe-se que o problema, AGP,  que visa minimizar o número de
guardas ou  câmeras suficientes para  visualmente cobrir uma
galeria  de  arte  é  NP-difícil; inclusive  para  polígonos
ortogonais.  Embora   piso  de  n/3   guardas  sejam  sempre
suficientes (e  em alguns casos  necessários) para polígonos
simples de  n lados, esse  resultado conduz a  algoritmos de
posicionamento,  mas não  de  minimização. Neste  seminário,
apresentaremos um  algoritmo exato  para o AGP  baseado numa
redução deste ao problema de cobertura de conjuntos que, uma
vez modelado  como um problema de  programação inteira, pode
ser resolvido em poucos  minutos para polígonos complexos de
até 2500 vértices.