`%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`

`%T An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem`

`%D 2007`

`%8 Oct. 7-10, 2007`

`%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`

`%E Falcão, Alexandre Xavier,`

`%E Lopes, Hélio Côrtes Vieira,`

`%B Brazilian Symposium on Computer Graphics and Image Processing, 20 (SIBGRAPI)`

`%C Belo Horizonte`

`%S Proceedings`

`%I IEEE Computer Society`

`%J Los Alamitos`

`%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`