Optimization Online


The Quest for Optimal Solutions for the Art Gallery Problem: a Practical Iterative Algorithm

D. C. Tozoni (davi.tozoni***at***gmail.com)
P. J. de Rezende (rezende***at***ic.unicamp.br)
C. C. de Souza (cid***at***ic.unicamp.br)

Abstract: The general Art Gallery Problem (AGP) consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented by a polygon. The AGP is a well known NP-hard problem and, for this reason, all algorithms proposed so far to solve it are unable to guarantee optimality except in especial cases. In this paper, we present a new method for solving the Art Gallery Problem by iteratively generating upper and lower bounds while seeking to reach an exact solution. Notwithstanding that convergence remains an important open question, our algorithm has been successfully tested on a very large collection of instances from publicly available benchmarks. Tests were carried out for several classes of instances totalizing more than a thousand hole-free polygons with sizes ranging from 20 to 1000 vertices. The proposed algorithm showed a remarkable performance, obtaining provably optimal solutions for every instance in a matter of minutes on a standard desktop computer. To our knowledge, despite the AGP having been studied for four decades within the field of computational geometry, this is the first time that an exact algorithm is proposed and extensively tested for this problem. Future research directions to expand the present work are also discussed.

Keywords: Art Gallery Problem, Point Guards, Exact Algorithms, Optimal Solutions, Computational Geometry, Integer Programming

Category 1: Combinatorial Optimization

Citation: Site: http://dx.doi.org/10.1007/978-3-642-38527-8_29 Bibtex entry: @incollection{ year={2013}, isbn={978-3-642-38526-1}, booktitle={Experimental Algorithms}, volume={7933}, series={Lecture Notes in Computer Science}, editor={Bonifaci, Vincenzo and Demetrescu, Camil and Marchetti-Spaccamela, Alberto}, doi={10.1007/978-3-642-38527-8_29}, title={The Quest for Optimal Solutions for the Art Gallery Problem: A Practical Iterative Algorithm}, url={http://dx.doi.org/10.1007/978-3-642-38527-8_29}, publisher={Springer Berlin Heidelberg}, author={Tozoni, DaviC. and Rezende, PedroJ. and Souza, CidC.}, pages={320-336} }


Entry Submitted: 01/16/2013
Entry Accepted: 01/19/2013
Entry Last Modified: 11/02/2013

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