Resolução do problema da galeria de arte: um método prático e robusto para o posicionamento ótimo de guardas-ponto

Author(s)

Davi Colli Tozoni

• Document type: Master's Dissertation
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2014-07-25

Examining board members

Cid Carvalho de Souza; Luiz Henrique de Figueiredo; Fábio Luiz Usberti

• Advisor: Pedro Jussieu de Rezende; Cid Carvalho de Souza

Abstract

In this dissertation, we present our research on the Art Gallery Problem (AGP), one of the most investigated problems in Computational Geometry. The AGP, which is a known NP-hard problem, consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented as a polygon. In the version of the problem treated in this work, usually called Art Gallery Problem with Point Guards, the guards can be placed anywhere in the polygon and the objective is to cover the whole region, which may or not have holes. We studied how to apply Computational Geometry concepts and algorithms as well as Integer Programming techniques in order to solve the AGP to optimality. This work culminated in the creation of a new algorithm for the AGP, whose idea is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. The algorithm was implemented and tested on more than 2800 instances of different sizes and classes of polygons. The technique was able to solve in minutes more than 90% of all instances considered, including polygons with thousands of vertices, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively as the one described here (AU)

• FAPESP's process: 12/18384-7 - Algorithms for Art Gallery Problems
• Grantee: Davi Colli Tozoni
• Support Opportunities: Scholarships in Brazil - Master