Solving the Art Gallery Problem: A Practical and Robust Method for Optimal Point Guard Positioning
Davi Colli Tozoni$^{1}$
$^{1}$University of Campinas. Sao Paulo Brazil
email: davi.tozoni@gmail.com

Schedule:Thu 22st@16:15, Room: A

This Master’s thesis focused on studying and developing techniques for optimally solving the Art Gallery Problem (AGP), one of the most investigated problems in Computational Geometry. The AGP, which is a known NP-hard problem, consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented as a polygon. We studied how to apply Computational Geometry concepts and algorithms as well as Integer Programming techniques in order to solve the AGP to optimality. This work culminated in the creation of a new algorithm for the AGP, whose idea is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP. The algorithm was implemented and tested on more than 2800 instances of different sizes and classes of polygons. The technique was able to solve in minutes more than 90% of all instances considered, including polygons with thousands of vertices, 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 as the one described here. For illustration, in a direct comparison with the algorithm by Kröller et al., considered one of the most promising techniques for the AGP, our method solved almost 32% more instances than its competitor.In addition, we provide a free version of our code and of our benchmark for download, which is unprecedented in the literature.

BibTex

@InProceedings{CLEI-2015:144526,
	author 		= {Davi Colli Tozoni},
	title 		= {Solving the Art Gallery Problem: A Practical and Robust Method for Optimal Point Guard Positioning},
	booktitle 	= {2015 XLI Latin American Computing Conference (CLEI), Special Edition},
	pages 		= {118--132},
	year 		= {2015},
	editor 		= {Universidad Católica San Pablo},
	address 	= {Arequipa-Peru},
	month 		= {October},
	organization 	= {CLEI},
	publisher 	= {CLEI},
	url 		= {http://clei.org/clei2015/144526},
	isbn 		= {978-9972-825-91-0},
	}