Please use this identifier to cite or link to this item:
Type: Artigo
Title: Algorithm 966: A Practical Iterative Algorithm For The Art Gallery Problem Using Integer Linear Programming
Author: Tozoni
Davi C.; de Rezende
Pedro J.; de Souza
Cid C.
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.
Subject: Design
Art Gallery Problem
Exact Algorithm
Combinatorial Optimization
Computational Geometry
Editor: Assoc Computing Machinery
New York
Citation: Acm Transactions On Mathematical Software. Assoc Computing Machinery, v. 43, p. , 2016.
Rights: fechado
Identifier DOI: 10.1145/2890491
Date Issue: 2016
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000384282800008.pdf1.84 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.