Close | |

@InProceedings{CoutoSouzReze:2007:ExEfAl, author = "Couto, Marcelo C. and Souza, Cid C. de and Rezende, Pedro J. de", affiliation = "Institute of Computing, State University of Campinas, Campinas - Brazil and Institute of Computing, State University of Campinas, Campinas - Brazil and Institute of Computing, State University of Campinas, Campinas - Brazil", title = "An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem", booktitle = "Proceedings...", year = "2007", editor = "Falc{\~a}o, Alexandre Xavier and Lopes, H{\'e}lio C{\^o}rtes Vieira", organization = "Brazilian Symposium on Computer Graphics and Image Processing, 20. (SIBGRAPI)", publisher = "IEEE Computer Society", address = "Los Alamitos", keywords = "Art Gallery, Exact Solution, Orthogonal Polygons, Integer Programming, Set Covering.", 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.", conference-location = "Belo Horizonte, MG, Brazil", conference-year = "7-10 Oct. 2007", doi = "10.1109/SIBGRAPI.2007.15", url = "http://dx.doi.org/10.1109/SIBGRAPI.2007.15", language = "en", ibi = "6qtX3pFwXQZG2LgkFdY/QGG9a", url = "http://urlib.net/ibi/6qtX3pFwXQZG2LgkFdY/QGG9a", targetfile = "couto-ArtGallery.pdf", urlaccessdate = "2024, Aug. 08" }

Close |