Theory, algorithms, and software for solving the 1.5D Terrain Guarding Problem.
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.
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}} }
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 |
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
Example: concavevalleys-10-01.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: concavevalleys-10-01.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 (non-manual) 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!