Optimization Online


A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming

DC Tozoni (davi.tozoni***at***gmail.com)
PJ de Rezende (rezende***at***ic.unicamp.br)
CC de Souza (cid***at***ic.unicamp.br)

Abstract: In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions make use of 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, an ILP based algorithm is proposed to optimally solve the Art Gallery Problem (AGP), one of the most intensely 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 three thousand 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.

Keywords: Art Gallery Problem, Exact Algorithm, Computational Geometry, Combinatorial Optimization

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Citation: Downloadable at http://doi.acm.org/10.1145/2890491 Davi C. Tozoni, Pedro J. De Rezende, and Cid C. De Souza. 2016. Algorithm 966: A Practical Iterative Algorithm for the Art Gallery Problem Using Integer Linear Programming. ACM Trans. Math. Softw. 43, 2, Article 16 (August 2016), 27 pages.


Entry Submitted: 10/31/2013
Entry Accepted: 11/01/2013
Entry Last Modified: 08/29/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society