<?xml version="1.0" encoding="ISO-8859-1"?>
<site>sibgrapi.sid.inpe.br 802</site>
<repository>sid.inpe.br/sibgrapi@80/2007/07.09.17.59</repository>
<citationkey>CoutoSouzReze:2007:ExEfAl</citationkey>
<title>An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem</title>
<format>Printed, On-line.</format>
<year>2007</year>
<date>Oct. 7-10, 2007</date>
<numberoffiles>1</numberoffiles>
<size>210 Kbytes</size>
<author>Couto, Marcelo C.,</author>
<author>Souza, Cid C. de,</author>
<author>Rezende, Pedro J. de,</author>
<affiliation>Institute of Computing, State University of Campinas, Campinas - Brazil</affiliation>
<affiliation>Institute of Computing, State University of Campinas, Campinas - Brazil</affiliation>
<affiliation>Institute of Computing, State University of Campinas, Campinas - Brazil</affiliation>
<editor>Falcão, Alexandre Xavier,</editor>
<editor>Lopes, Hélio Côrtes Vieira,</editor>
<conferencename>Brazilian Symposium on Computer Graphics and Image Processing, 20 (SIBGRAPI)</conferencename>
<conferencelocation>Belo Horizonte</conferencelocation>
<booktitle>Proceedings</booktitle>
<publisher>IEEE Computer Society</publisher>
<tertiarytype>Full Paper</tertiarytype>
<transferableflag>1</transferableflag>
<contenttype>External Contribution</contenttype>
<keywords>Art Gallery, Exact Solution, Orthogonal Polygons, Integer Programming, Set Covering.</keywords>
<abstract>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.</abstract>
<language>en</language>
<targetfile>couto-ArtGallery.pdf</targetfile>
<visibility>shown</visibility>
<mirrorrepository>dpi.inpe.br/banon-pc2@80/2006/08.30.19.27</mirrorrepository>
<hostcollection>sid.inpe.br/banon/2001/03.30.15.38</hostcollection>
<lasthostcollection>sid.inpe.br/banon/2001/03.30.15.38</lasthostcollection>
<url>http://sibgrapi.sid.inpe.br/rep-/sid.inpe.br/sibgrapi@80/2007/07.09.17.59</url>