| Full text | |
| Author(s): |
Tozoni, Davi C.
;
de Rezende, Pedro J.
;
de Souza, Cid C.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE; v. 43, n. 2 SEP 2016. |
| Web of Science Citations: | 1 |
| Abstract | |
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) | |
| FAPESP's process: | 07/52015-0 - Approximation methods for visual computing |
| Grantee: | Jorge Stolfi |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 12/18384-7 - Algorithms for Art Gallery Problems |
| Grantee: | Davi Colli Tozoni |
| Support Opportunities: | Scholarships in Brazil - Master |