Strategies for Optimal Placement of Surveillance Cameras in Art Galleries

The Art Gallery problem (AGP) consists of minimizing the num-ber 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 prob-lems (SCPs) corresponding to discretizations of P. Besides hav-ing proven in [Couto et al. 2007] that this procedure always con-verges 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 discretiz-ing 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