<?xml version="1.0" encoding="ISO-8859-1"?>
<metadatalist>
	<metadata ReferenceType="Conference Proceedings">
		<repository>sid.inpe.br/sibgrapi@80/2007/07.09.17.59</repository>
		<metadatarepository>sid.inpe.br/sibgrapi@80/2007/07.09.17.59.10</metadatarepository>
		<site>sibgrapi.sid.inpe.br 802</site>
		<citationkey>CoutoSouzReze:2007:ExEfAl</citationkey>
		<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>
		<title>An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem</title>
		<conferencename>Brazilian Symposium on Computer Graphics and Image Processing, 20 (SIBGRAPI)</conferencename>
		<year>2007</year>
		<editor>Falcão, Alexandre Xavier,</editor>
		<editor>Lopes, Hélio Côrtes Vieira,</editor>
		<booktitle>Proceedings</booktitle>
		<date>Oct. 7-10, 2007</date>
		<publisheraddress>Los Alamitos</publisheraddress>
		<publisher>IEEE Computer Society</publisher>
		<conferencelocation>Belo Horizonte</conferencelocation>
		<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>
		<tertiarytype>Full Paper</tertiarytype>
		<format>Printed, On-line.</format>
		<size>210 Kbytes</size>
		<numberoffiles>1</numberoffiles>
		<targetfile>couto-ArtGallery.pdf</targetfile>
		<lastupdate>2007:07.09.17.59.09 sid.inpe.br/banon/2001/03.30.15.38 administrator</lastupdate>
		<metadatalastupdate>2020:02.19.03.06.18 sid.inpe.br/banon/2001/03.30.15.38 administrator {D 2007}</metadatalastupdate>
		<mirrorrepository>dpi.inpe.br/banon-pc2@80/2006/08.30.19.27</mirrorrepository>
		<usergroup>cid@ic.unicamp.br administrator</usergroup>
		<visibility>shown</visibility>
		<transferableflag>1</transferableflag>
		<hostcollection>sid.inpe.br/banon/2001/03.30.15.38</hostcollection>
		<contenttype>External Contribution</contenttype>
		<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>
	</metadata>
</metadatalist>