Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

An exact algorithm for minimizing vertex guards on art galleries

Texto completo
Autor(es):
Couto, Marcelo C. [1] ; de Rezende, Pedro J. [1] ; de Souza, Cid C. [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, BR-13083852 Campinas, SP - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: International Transactions in Operational Research; v. 18, n. 4, p. 425-448, JUL 2011.
Citações Web of Science: 15
Resumo

We 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. (AU)

Processo FAPESP: 07/52015-0 - Métodos de aproximação para computação visual
Beneficiário:Jorge Stolfi
Linha de fomento: Auxílio à Pesquisa - Temático