Advanced search
Start date

Algorithms for Art Gallery Problems

Grant number: 12/18384-7
Support type:Scholarships in Brazil - Master
Effective date (Start): January 01, 2013
Effective date (End): March 31, 2014
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Cid Carvalho de Souza
Grantee:Davi Colli Tozoni
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil
Associated scholarship(s):13/13534-3 - Algorithms for art gallery problems, BE.EP.MS


The Art Gallery Problem consists in finding the minimum number of guards sufficient to completely cover the interior of an art gallery, represented by a polygon of n vertices. By the fact that the AGP is a proven NP-Hard problem, it is normally treated using heuristics or approximation algorithms, which does not guarantee optimality. The objective of this project is to study and develop a new approach for solving the Art Gallery Problem. The establishment of new techniques for solving the AGP could bring significant advances in many application areas including wireless sensor network, where coverage of regions and positioning of nodes are major challenges.

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
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, . (07/52015-0, 12/18384-7)
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
TOZONI, Davi Colli. Resolução do problema da galeria de arte: um método prático e robusto para o posicionamento ótimo de guardas-ponto. 2014. Master's Dissertation - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.

Please report errors in scientific publications list by writing to: