Return to project main page

AGPPROJ: The Art Gallery Problem With Point Guards, by D. C. Tozoni, P. J. de Rezende and C. C. de Souza

Citing this page:

    Use the BibTeX entry:

    @Misc{art-gallery-unicamp-page,
     author = {Davi C. Tozoni and Pedro J. de Rezende and Cid C. de Souza},
     title = {The {Art Gallery Problem} Project},
     year = {2013},
     note = {\sl{www.ic.unicamp.br/$\sim$cid/Problem-instances/Art-Gallery/AGPPG}}
    }


Abstract

The aim of this research group is to develop a new method for solving the Art Gallery Problem With Point-Guards. The AGP is a well known NP-hard problem and, for this reason, its solutions are usually heuristics based, which do not guarantee optimal solutions. Some nice outcomes were already obtained by the researcher group, including some theoretical results and the development and implementation of a new technique that is capable of solving to optimality the vast majority of benchmark instances in literature.


Work Description

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

The first AGP problem studied by the research group at Unicamp 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 previous publications, the objective was to construct an exact algorithm for AGPVG and, as a consequence, a fast algorithm with proven convergence was developed and tested.

Then, in 2011, the research group began working on the Art Gallery Problem with Point Guards (AGPPG or simply AGP), which is the most general version of the AGP, where the guards can be placed anywhere in the interior of the input polygon (including also the boundary). The idea obtained used in the resolution of AGPVG was adapted and incremented to construct a new method, which is able to find exact solutions for the AGP With Point-Guards. Currently, an algorithm has already been implemented and tested and has shown great results in comparison with other state of art techniques.

The picture on the left displays a summary of our technique and the animation on the right side shows and execution example of our current method for solving the AGP With Point Guards. More information about our techniques and also about AGP can be found in [1] and [2].
The research group that is working on the Art Gallery Problem with Points Guards is presented below:
  • Davi Colli Tozoni
  • Pedro Jussieu de Rezende
  • Cid Carvalho de Souza


Implementation

After designing the algorithm, a software was implemented to allow computational testing. The program was developed in C++ coding language and using the library CGAL (Computational Geometry Algorithms Library) for dealing with geometric tasks, such as: visibility operations, arrangements constructions, partitioning of polygons and other geometric tasks. Furthermore, the ILP Solvers XPRESS Optimization Suite and GLPK (GNU Linear Programming Kit) were also employed to solve ILP models of the Set Cover Problem, which is used in our method as a representation of a discretized version of AGP.

Our code that implements the idea presented in [3] is available and can be downloaded at the link below:


Instances AGP2013

Instances with holes were created for testing our algorithm. Two generators (gB and gD) were developed to obtain a total of 390 polygons, with sizes between 100 and 5000 vertices. The instances produced using gB and gD can be downloaded below:
  • simple polygons with simple holes, using gB generator (Developed by Bruno Espinosa Crepaldi) - instances[.tar.gz]
  • simple polygons with simple holes, using gD generator - instances[.tar.gz]
  • orthogonal polygons with orthogonal holes, using gD generator - instances[.tar.gz]

Polygons without holes were also tested in our experiments. Most of these instances were created by the research group at Unicamp while solving AGPFC and can be found here.
Moreover, with the growing improvement in the performance of our solution, it became necessary to test larger and more complex instances. That said, we decided to employ the existing generators used in our AGPVG research to create polygons (without holes) of 5000 vertices. These instances can be downloaded below:

Finally, during this project, we also experimented our implementation on instances produced by other research groups. Among those are the interesting spike polygons, which were developed by researchers from Technische Universität Braunschweig (TUBs). Below you find a package kindly provided by Professor Dr. Alexander Kröller containing all 210 spike instances used in our tests.



File Format of Instances

Each file consists of one line divided in four parts. The first part is an integer value that represents the number of vertices of the boundary.
The second part is a counterclockwise sequence of the vertices of the boundary. Each vertex is represented by its x and y coordinates each of which is written as the quotient of two integers int/int.

After all the information about the boundary has been placed, the number of holes is presented, followed by a sequence of the representation of each hole, with the same format used for the boundary.


References




Contacts

  • Davi Colli Tozoni:    
  • Pedro Jussieu de Rezende:     homepage    
  • Cid Carvalho de Souza:     homepage    

Research supported by: