@techreport{TR-IC-09-46,
   number = {IC-09-46},
   author  =  {Marcelo C. {Couto} and Pedro J. {de Rezende} and Cid C.
                   {de Souza}},
   title = {An Exact Algorithm for an Art Gallery Problem},
   month = {November},
   year = {2009},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 25 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       We consider an Art Gallery problem (AGP) which aims to minimize
       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 {\em 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 to our previous experiments, which were
       already five times larger than those previously reported in the
       literature.
  }
}