AGPPROJ - Art Gallery Problem Project, by P. J. de Rezende, C. C. de Souza, M. C. Couto and D. C. Tozoni
AbstractThe aim of this project is to study and design new exact techniques for solving the Art Gallery Problem (AGP) and its variants. The 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, its solutions have usually been heuristics based, which does not guarantee optimal solutions. Among the advances achieved by our research group are theoretical results and the development and implementation of models that solve to optimality very large instances within a few minutes of computation.
Problem DescriptionThe Art Gallery Problem was initially proposed by Victor Klee in 1973 as the question of determining the minimum number of guards sufficient to watch over an entire art gallery, represented by a n-wall simple polygon. The Problem's input consists of a simple polygon, representing the outline of an art gallery, and one seeks to find a smallest set of points where guards (or cameras) should be placed so that the entire polygon is visually covered.
Over the years, many variations of the AGP were proposed based on modifications to the objectives and restrictions of the original problem. Some of the most studied AGP variants are:
- The Art Gallery Problem with Point Guards
- The Art Gallery Problem with Vertex Guards
- The Art Gallery Problem with Edge Guards
- The Edge Covering Problem
- The Fortress Problem
The project developed at Unicamp deals with some of these different versions of the problem. Below, we present details on what has been done and what the current state of the investigation on each of these problems are.
Art Gallery Problem with Vertex GuardsThe first AGP problem studied by this research group was the Art Gallery Problem with Vertex Guards (AGPVG), whose goal is to minimize the number of vertex guards required to watch an art gallery whose boundary is an n-vertex polygon P. Unlike other research that has appeared in the literature, the objective here was to design an exact algorithm. We presented in  an algorithm that iteratively computes optimal solutions to Set Cover Problems (SCPs) corresponding to discretizations of P. While it is shown, in , that this procedure converges to an exact solution to the original continuous problem, the number of iterations executed is highly dependent on the way we discretize the polygon. Although the best theoretical bound for convergence is O(n³) iterations, we show that, in practice, it is achieved after a small number of them, even for random polygons of thousand of vertices.
To read more about our solution to the AGPVG and to download our large benchmark of instances, click here.
Art Gallery Problem with Point GuardsSince 2011, our group started working on the Art Gallery Problem with Point Guards (AGPPG), which is a more general version of the AGP, where the guards may be positioned at any point in the interior or boundary of the input polygon. As before, we seek to find exact solutions to the AGPPG. Currently, an algorithm is being implemented and tested. Up to this point, some very nice results have been obtained [7,9].
To read more about our method for solving the AGPPG and to access downloadable material, click here.
-  An Exact and Efficient Algorithm for the Orthogonal Art Gallery Problem, M. C. Couto, C. C. de Souza and P. J. de Rezende, 2007, SIBGRAPI.
-  Experimental Evaluation of an Exact Algorithm for the Orthogonal Art Gallery Problem, M. C. Couto, C. C. de Souza and P. J. de Rezende, 2008, WEA.
-  Strategies for Optimal Placement of Surveillance Cameras in Art Galleries, M. C. Couto, C. C. de Souza and P. J. de Rezende, 2008, GraphiCon.
-  An IP solution to the art gallery problem, M. C. Couto, P. J. de Rezende and C. C. de Souza, 2009, Symposium on Computational Geometry (see also the accompanying video).
-  An Exact Algorithm for an Art Gallery Problem, M. C. Couto, P. J. de Rezende and C. C. de Souza, 2009, Technical Report 2009-46 (pdf, bib, abstract). Submitted for publication.
-  An exact algorithm for minimizing vertex guards on art galleries, M. C. Couto, P. J. de Rezende and C. C. de Souza, 2011, ITOR.
-  The Quest for Optimal Solutions for the Art Gallery Problem: A Practical Iterative Algorithm, D. C. Tozoni, P. J. de Rezende and C. C. de Souza, 2013, SEA.
-  Point guards and point clouds: solving general art gallery problems, D. Borrmann, P. J. de Rezende, C. C. de Souza, Cid C. and S. P. Fekete, S. Friedrichs, A. Kröller, A. Nüchter, C. Schmidt and D. C. Tozoni, 2013, Twenty-ninth Annual Symposium on Computational Geometry (see also the accompanying video).
-  A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming, D. C. Tozoni, P. J. de Rezende, C. C. de Souza, 2013, Optimization Online.