An exact algorithm for minimizing vertex guards on art galleries

dc.creatorCouto, MC
dc.creatorde Rezende, PJ
dc.creatorde Souza, CC
dc.date2011
dc.dateJUL
dc.date2014-07-30T13:48:39Z
dc.date2015-11-26T18:06:20Z
dc.date2014-07-30T13:48:39Z
dc.date2015-11-26T18:06:20Z
dc.date.accessioned2018-03-29T00:48:32Z
dc.date.available2018-03-29T00:48:32Z
dc.identifierInternational Transactions In Operational Research. Wiley-blackwell, v. 18, n. 4, n. 425, n. 448, 2011.
dc.identifier0969-6016
dc.identifierWOS:000294308900001
dc.identifier10.1111/j.1475-3995.2011.00804.x
dc.identifierhttp://www.repositorio.unicamp.br/jspui/handle/REPOSIP/54397
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/54397
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1293333
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionWe consider the problem [art gallery problem (AGP)] of minimizing the number of vertex guards required to monitor an art gallery whose boundary is an n-vertex simple polygon. In this paper, we compile and extend our research on exact approaches for solving the AGP. In prior works, we proposed and tested an exact algorithm for the case of orthogonal polygons. In that algorithm, a discretization that approximates the polygon is used to formulate an instance of the set cover problem, which is subsequently solved to optimality. Either the set of guards that characterizes this solution solves the original instance of the AGP, and the algorithm halts, or the discretization is refined and a new iteration begins. This procedure always converges to an optimal solution of the AGP and, moreover, the number of iterations executed highly depends on the way we discretize the polygon. Notwithstanding that the best known theoretical bound for convergence is Theta(n(3)) iterations, our experiments show that an optimal solution is always found within a small number of them, even for random polygons of many hundreds of vertices. Herein, we broaden the family of polygon classes to which the algorithm is applied by including non-orthogonal polygons. Furthermore, we propose new discretization strategies leading to additional trade-off analysis of preprocessing vs. processing times and achieving, in the case of the novel Convex Vertices strategy, the most efficient overall performance so far. We report on experiments with both simple and orthogonal polygons of up to 2500 vertices showing that, in all cases, no more than 15 minutes are needed to reach an exact solution, on a standard desktop computer. Ultimately, we more than doubled the size of the largest instances solved to optimality compared with our previous experiments, which were already five times larger than those previously reported in the literature.
dc.description18
dc.description4
dc.description425
dc.description448
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionFAEPEX/Unicamp
dc.descriptionConselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
dc.descriptionFundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)
dc.descriptionCNPq [301732/2007-8, 472504/2007-0, 483177/2009-1, 473867/2010-9]
dc.descriptionFAPESP [07/52015-0]
dc.languageen
dc.publisherWiley-blackwell
dc.publisherMalden
dc.publisherEUA
dc.relationInternational Transactions In Operational Research
dc.relationInt. Trans. Oper. Res.
dc.rightsfechado
dc.rightshttp://olabout.wiley.com/WileyCDA/Section/id-406071.html
dc.sourceWeb of Science
dc.subjectart gallery problem
dc.subjectexact algorithm
dc.subjectset covering
dc.subjectvisibility
dc.subjectApproximation Algorithms
dc.subjectVisibility
dc.subjectPolygons
dc.subjectCoverage
dc.titleAn exact algorithm for minimizing vertex guards on art galleries
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución