Return to project main page

AGPLIB - Art Gallery Problem Library, by M. C. Couto, P. J. de Rezende and C. C. de Souza

Citing this page:

    Use the BibTeX entry:

    @Misc{art-gallery-instances-page,
     author = {Marcelo C. Couto and Pedro J. de Rezende and Cid C. de Souza},
     title = {Instances for the {Art Gallery Problem}},
     year = {2009},
     note = {\sl{www.ic.unicamp.br/$\sim$cid/Problem-instances/Art-Gallery}}
    }

Short problem description

The Art Gallery Problem (AGP) is a well-known NP-hard problem. Given a simple polygon P that bounds an art gallery, we are asked to determine the minimum number of guards sufficient to keep the whole gallery under surveillance.

What is in this library

AGPLIB is a library of sample instances for the AGP problem consisting of various classes of polygons of multiple sizes, which were the test bed for the results in papers [1], [2], [3], [4], [5].

For each set of instances available below, the corresponding results are also shown.

File Format: Instances

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

As an example, here is the representation of a square with coordinates (1, 1) (50, 1) (50, 50) and (1, 50):
        4   1/1   1/1   100/2   1/1   500/10   50/1   1/1   100/2

File Format: Results

Each file consists of one csv table with the following values: instance ID (=filename), number of vertices, strategy applied to solve the instance, number of iterations to achieve the optimal solution, number of guards in the optimal solution found, preprocessing time, processing time and the total time of the algorithm used to optimally solve the instance.

Instances AGP2009b

Additional interesting instances:

These results correspond to runs executed on: Pentium IV 3.4GHz, 3 Gb RAM, Linux 2.6.24, CGAL 3.2.1, Xpress 18.10.04.

Instances AGP2009a

Instances and results presented in the papers:

A total of 1804 AGP instances, each one having between 20 and 2500 vertices, grouped into four classes:

These results correspond to runs executed on: Pentium IV 3.4GHz, 3 Gb RAM, Linux 2.6.24, CGAL 3.2.1, Xpress 18.10.04.

Instances AGP2008b

Instances and results presented in the paper Strategies for Optimal Placement of Surveillance Cameras in Art Galleries, M. C. Couto, C. C. de Souza and P. J. de Rezende, 2008, GraphiCon.

A total of 643 AGP instances, each one having between 20 and 1000 vertices, grouped into three classes:

These results correspond to runs executed on: Pentium IV 3.4GHz, 1 Gb RAM, Linux 2.6.17, CGAL 3.2.1, Xpress 17.01.02.

Instances AGP2008a

Instances and results presented in the paper 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.

A total of 1833 AGP instances, each one having between 20 and 1000 vertices, grouped into four classes:

These results correspond to runs executed on: Pentium IV 3.4GHz, 1 Gb RAM, Linux 2.6.17, CGAL 3.2.1, Xpress 17.01.02.

Instances AGP2007

Instances and results presented in the paper 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.

There is a total of 10282 AGP instances, each one having between 8 and 200 vertices, grouped into three classes:

These results correspond to runs executed on: Pentium IV 2.66GHz, 1 Gb RAM, CGAL 3.2.1, Xpress 17.01.02.

References

Address

Marcelo C. Couto, Cid C. de Souza, and Pedro J. de Rezende
Universidade Estadual de Campinas
Instituto de Computação
Avenida Albert Einstein, 1251
13083-852 Campinas, SP, Brasil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: