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: