Close
Metadata

Identity statement area
Reference TypeConference Paper (Conference Proceedings)
Sitesibgrapi.sid.inpe.br
Repositorysid.inpe.br/sibgrapi@80/2007/07.09.17.59
Last Update2007:07.09.17.59.09 administrator
Metadatasid.inpe.br/sibgrapi@80/2007/07.09.17.59.10
Metadata Last Update2020:02.19.03.06.18 administrator
Citation KeyCoutoSouzReze:2007:ExEfAl
TitleAn Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem
FormatPrinted, On-line.
Year2007
DateOct. 7-10, 2007
Access Date2021, Jan. 16
Number of Files1
Size210 KiB
Context area
Author1 Couto, Marcelo C.
2 Souza, Cid C. de
3 Rezende, Pedro J. de
Affiliation1 Institute of Computing, State University of Campinas, Campinas - Brazil
2 Institute of Computing, State University of Campinas, Campinas - Brazil
3 Institute of Computing, State University of Campinas, Campinas - Brazil
EditorFalcão, Alexandre Xavier
Lopes, Hélio Côrtes Vieira
Conference NameBrazilian Symposium on Computer Graphics and Image Processing, 20 (SIBGRAPI)
Conference LocationBelo Horizonte
Book TitleProceedings
PublisherIEEE Computer Society
Publisher CityLos Alamitos
Tertiary TypeFull Paper
History2007-07-09 17:59:10 :: cid@ic.unicamp.br -> administrator ::
2007-08-02 21:17:16 :: administrator -> cid@ic.unicamp.br ::
2008-07-17 14:09:42 :: cid@ic.unicamp.br -> administrator ::
2009-08-13 20:38:18 :: administrator -> banon ::
2010-08-28 20:02:26 :: banon -> administrator ::
2020-02-19 03:06:18 :: administrator -> :: 2007
Content and structure area
Is the master or a copy?is the master
Content Stagecompleted
Transferable1
Content TypeExternal Contribution
KeywordsArt Gallery, Exact Solution, Orthogonal Polygons, Integer Programming, Set Covering.
AbstractIn 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 $ nleq 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.
source Directory Contentthere are no files
agreement Directory Contentthere are no files
Conditions of access and use area
data URLhttp://urlib.net/rep/sid.inpe.br/sibgrapi@80/2007/07.09.17.59
zipped data URLhttp://urlib.net/zip/sid.inpe.br/sibgrapi@80/2007/07.09.17.59
Languageen
Target Filecouto-ArtGallery.pdf
User Groupcid@ic.unicamp.br
administrator
Visibilityshown
Allied materials area
Mirror Repositorydpi.inpe.br/banon-pc2@80/2006/08.30.19.27
Host Collectionsid.inpe.br/banon/2001/03.30.15.38
Notes area
Empty Fieldsaccessionnumber archivingpolicy archivist area callnumber copyholder copyright creatorhistory descriptionlevel dissemination documentstage doi e-mailaddress edition electronicmailaddress group holdercode isbn issn label lineage mark nextedition nexthigherunit notes numberofvolumes orcid organization pages parameterlist parentrepositories previousedition previouslowerunit progress project readergroup readpermission resumeid rightsholder secondarydate secondarykey secondarymark secondarytype serieseditor session shorttitle sponsor subject tertiarymark type url versiontype volume

Close