@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",
conference-year = "Oct. 7-10, 2007",
language = "en",
targetfile = "couto-ArtGallery.pdf",
urlaccessdate = "2021, Jan. 16"
}