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