Theory, algorithms, and software for solving the 1.5D Terrain Guarding Problem.
The 1.5D Terrain Guarding Problem (TGP) asks how to cover an xmonotone 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 AGPlike 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.
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 20150806}, year = {2015}, month = {August}, howpublished = {\url{http://resources.mpiinf.mpg.de/tgp/index.html\#instances}} }
There are four main instance classes: parabolawalk instances have visibility regions that interact in complex ways, concavevalleys encourage the placement of nonvertex 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 
The instance files are named classnm.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 classnm.solution.vertex or classnm.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 xcoordinate followed by a whitespace and a ycoordinate. The x and ycoordinates 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 vertexguards. 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 xcoordinate followed by a whitespace and a ycoordinate, 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 doublechecked by a verification algorithm.
Example: concavevalleys1001.terrain
Example: concavevalleys1001.solution.vertex10 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: concavevalleys1001.solution.pointvertex guards 2 3.82127 47.7359 5.52574 56.87
point guards 1 10.2712 78.1794
The scripts (python and some bash) used to generate the (nonmanual) instances are included in the TGPIL. They can be easily modified to generate larger instances of the existing classes.
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.
Our software heavily relies on these software libraries:
These are the people most actively involved in the Terrain Guarding Project. Feel free to contact us!