Please use this identifier to cite or link to this item:
Type: Artigo de evento
Title: Strategies For Optimal Placement Of Surveillance Cameras In Art Galleries
Author: Couto M.C.
De Souza C.C.
De Rezende P.J.
Abstract: The Art Gallery problem (AGP) consists of minimizing the number of cameras required to guard an art gallery whose boundary is an n-vertex polygon P. In this paper, we report our ongoing work in exploring an exact algorithm for a few variants of AGP, which iteratively computes optimal solutions to Set Cover problems (SCPs) corresponding to discretizations of P. Besides having proven in [Couto et al. 2007] that this procedure always converges to an exact solution of the original continuous problem, we have evidence that, in practice, convergence is achieved after only a few iterations, even for random polygons of hundreds of vertices. Nonetheless, we observe that the number of iterations required is highly dependent on the way P is initially discretized. As each iteration involves the solution of an SCP, the strategy for discretizing P is of paramount importance. We present here some of the discretization strategies we have been working with and new ones that will be studied in the near future. In comparison to the current literature, our results show a significant improvement in the size of the instances that can be solved to optimality while maintaining low execution times: no more than 65 seconds for random polygons of up to one thousand vertices.
Rights: fechado
Identifier DOI: 
Date Issue: 2008
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.