Algoritmos para Problemas de Galeria de Arte

• Processo: 12/18384-7
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de janeiro de 2013
• Data de Término da vigência: 31 de março de 2014
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Davi Colli Tozoni
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Bolsa(s) vinculada(s): 13/13534-3 - Algoritmos para problemas da galeria de arte, BE.EP.MS
• Assunto(s): Geometria computacional Redes de sensores Visibilidade Heurística
• Palavra(s)-Chave do Pesquisador: Algoritmo Exato | Geometria Computacional | heurística | Problema da galeria de arte | rede de sensores | visibilidade | Geometria Computacional

Resumo

O Problema da Galeria de Arte (Art Gallery Problem - AGP) consiste em determinar o número mínimo de guardas suficientes para vigiar toda uma galeria de arte, representada por um polígono de n vértices. Pelo fato do AGP ser provadamente um problema NP-difícil, ele é normalmente tratado com heurísticas e algoritmos de aproximação, que não garantem otimalidade das soluções. Este projeto tem como objetivo o estudo e a elaboração de uma nova técnica para a resolução do problema da Galeria de Arte. O desenvolvimento de novas técnicas para resolver o AGP traria grandes avanços em diversos campos de pesquisa como, por exemplo, a área de redes de sensores wireless, na qual a cobertura das regiões e o posicionamento dos nós são questões de extrema importância.

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

TOZONI, DAVI C.; DE REZENDE, PEDRO J.; DE SOUZA, CID C.. Algorithm 966: A Practical Iterative Algorithm for the Art Gallery Problem Using Integer Linear Programming. ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, v. 43, n. 2, SEP 2016. (07/52015-0, 12/18384-7)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

TOZONI, Davi Colli. Solving the art gallery problem: a practical and robust method for optimal point guard positioning = Resolução do problema da galeria de arte: um método prático e robusto para o posicionamento ótimo de guardas-ponto. 2014. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.