Título: An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem

Palestrante: Marcelo Couto

Sexta-feira, 14 de setembro, 16h, sala 85

Resumo

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\le 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.