%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi@80/2007/07.09.17.59
%2 sid.inpe.br/sibgrapi@80/2007/07.09.17.59.10
%A Couto, Marcelo C.,
%A Souza, Cid C. de,
%A Rezende, Pedro J. de,
%@affiliation Institute of Computing, State University of Campinas, Campinas - Brazil
%@affiliation Institute of Computing, State University of Campinas, Campinas - Brazil
%@affiliation Institute of Computing, State University of Campinas, Campinas - Brazil
%T An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem
%B Brazilian Symposium on Computer Graphics and Image Processing, 20 (SIBGRAPI)
%D 2007
%E Falcăo, Alexandre Xavier,
%E Lopes, Hélio Côrtes Vieira,
%S Proceedings
%8 Oct. 7-10, 2007
%J Los Alamitos
%I IEEE Computer Society
%C Belo Horizonte
%K Art Gallery, Exact Solution, Orthogonal Polygons, Integer Programming, Set Covering.
%X In this paper, we propose an exact algorithm to solve the Orthogonal Art Gallery problem in which guards can only be placed on the vertices of the polygon $P$ representing the gallery. Our approach is based on a discretization of $P$ into a finite set of points in its interior. The algorithm repeatedly solves an instance of the Set Cover problem obtaining a minimum set $Z$ of vertices of $P$ that can view all points in the current discretization. Whenever $P$ is completely visible from $Z$ , the algorithm halts; otherwise, the discretization is refined and another iteration takes place. We establish that the algorithm always converges to an optimal solution by presenting a worst case analysis of the number of iterations that could be effected. Even though these could theoretically reach $O(n^4)$ , our computational experiments reveal that, in practice, they are linear in $n$ and, for $n\leq 200$ , they actually remain less than three in almost all instances. Furthermore, the low number of points in the initial discretization, $O(n^2)$ , compared to the possible $O(n^4)$ atomic visibility polygons, renders much shorter total execution times. Optimal solutions found for different classes of instances of polygons with up to 200 vertices are also described.
%@language en
%3 couto-ArtGallery.pdf