An Exact Algorithm for an Art Gallery Problem
Resumo
In this master thesis, a geometrical NP-HARD problem, the Art Gallery problem, is studied. The problem goal is to minimize the number of guards sufficient to cover the interior of an art gallery whose boundary is represented by a simple polygon. Among the many variants, we focus on one where the guards are stationary and restricted to vertices of the polygon, which can be either orthogonal or general simple, without holes. An exact algorithm is proposed in which the original continuous problem is discretized. Proofs of correctness and convergence of the algorithm to an optimal solution are given. Extensive experimentation with the algorithm show that it solves to optimality instances with more than ten times the size of the largest ones reported earlier in the literature.
Referências
Lee, D. T. and Lin, A. K. (1986). Computational complexity of art gallery problems. IEEE Trans. Inf. Theor., 32(2):276–282.
O’Rourke, J. (1987). Art Gallery Theorems and Algorithms. Oxford University Press.
Urrutia, J. (2000). Art gallery and illumination problems. In Sack, J.-R. and Urrutia, J., editors, Handbook of Computational Geometry, pages 973–1027. North-Holland.
