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.)

Algorithm 966: A Practical Iterative Algorithm for the Art Gallery Problem Using Integer Linear Programming

Texto completo
Autor(es):
Tozoni, Davi C. ; de Rezende, Pedro J. ; de Souza, Cid C.
Número total de Autores: 3
Tipo de documento: Artigo Científico
Fonte: ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE; v. 43, n. 2 SEP 2016.
Citações Web of Science: 1
Resumo

In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions use Integer Linear Programming (ILP) modeling and rely on state-of-the-art solvers to be able to find optimal solutions for large instances in a matter of minutes. In this work, we discuss an ILP-based algorithm that solves to optimality the Art Gallery Problem (AGP), one of the most studied problems in computational geometry. The basic idea of our method is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. Our algorithm was implemented and tested on almost 3,000 instances and attained optimal solutions for the vast majority of them, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively and efficiently as the one described here. Evidence of its robustness is presented through tests done on a number of classes of polygons of various sizes with and without holes. A software package implementing the algorithm is made available. (AU)

Processo FAPESP: 12/18384-7 - Algoritmos para problemas de galeria de arte
Beneficiário:Davi Colli Tozoni
Linha de fomento: Bolsas no Brasil - Mestrado
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