max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Project Homepage


The Terrain Guarding Project

Theory, algorithms, and software for solving the 1.5D Terrain Guarding Problem.

Guard Placement Guard Filter

About


The 1.5D Terrain Guarding Problem (TGP) asks how to cover an x-monotone chain of line segments with as few guards as possible.

TGP is a variant of the famous Art Gallery Problem (AGP) which has received much attention over the last decades. The AGP has various applications, it does, however, neglect height information. Dropping one dimension of the Art Gallery Problem and replacing it with height information yields the Terrain Guarding Problem. Our motivation is to develop the techniques necessary to deal with height information in an AGP-like problem, paving the way to eventually add height information to the AGP.

We develop theory, algorithms, and software to efficiently solve large instances the Terrain Guarding Problem.


Resources


The Terrain Guarding Problem Instance Library

We want our test instances to be publicly available for future testing. The Terrain Guarding Problem Instance Library (TGPIL) is available in the following versions (all downloads come without any warranty whatsoever):

Please use this bibtex entry to cite the Terrain Guarding Problem Instance Library:

@misc{tgpil,
  author       = {Stephan Friedrichs and Michael Hemmer and Christiane Schmidt},
  title        = {Terrain Guarding Problem Instance Library},
  note         = {Version 2015-08-06},
  year         = {2015},
  month        = {August},
  howpublished = {\url{http://resources.mpi-inf.mpg.de/tgp/index.html\#instances}}
}

Instance Classes

There are four main instance classes: parabolawalk instances have visibility regions that interact in complex ways, concavevalleys encourage the placement of non-vertex guards, walk is a simple random walk which is also used as noise on other instances, and sinewalk is a noisy sine function. Besides, there are some isolated test instances and some based on the Blancmange curve. A detailed description is available in our publications.


parabolawalk instance

concavevalleys instance

walk instance

sinewalk instance

File Format

The instance files are named class-n-m.terrain, where class is the instance class, n is the number of vertices, and m instance's number. If an optimal vertex guard or point guard solution is available, it is stored in a solution file named class-n-m.solution.vertex or class-n-m.solution.point, respectively.

Each instance or solution file contains ASCII text. An instance file contains a single integer in the first line, denoting the number of vertices. After that there is one line for each vertex, containing an x-coordinate followed by a whitespace and a y-coordinate. The x- and y-coordinates are either integer or floating point.

A solution file starts with a line either saying "vertex guards" or "point guards", depending on whether the solution is for point- or vertex-guards. Then there is a line containing a single integer stating the number of points. This is followed by one line for each guard, containing an x-coordinate followed by a whitespace and a y-coordinate, as for the instances.

Note that solution files are not available for every instance, since we do not include every solution our software ever found, but only those solutions that have been double-checked by a verification algorithm.

Example: concavevalleys-10-01.terrain

10
0.0 -29.699830882249962
3.8212651035691074 -47.73594632240078
5.525742325651239 -56.87000545991599
8.080008722137896 -79.413384273812
23.59483648530883 -70.67591691226546
26.72727516566714 -56.92879111652525
28.047092494521916 -53.07099354721832
31.662654441384632 -44.24465301957117
32.22302572131207 -43.14578793038501
36.0 -36.34397539543574
Example: concavevalleys-10-01.solution.vertex
vertex guards
2
3.82127 -47.7359
5.52574 -56.87
Example: concavevalleys-10-01.solution.point
point guards
1
10.2712 -78.1794

Generator Scripts

The scripts (python and some bash) used to generate the (non-manual) instances are included in the TGPIL. They can be easily modified to generate larger instances of the existing classes.

Software

Not all dependencies of our software have been officially released, yet. Hence, a release from our side is not particularly helpful. However, feel free to contact us if you are interested in the code.

Libraries

Our software heavily relies on these software libraries:


People


These are the people most actively involved in the Terrain Guarding Project. Feel free to contact us!


Publications