Interactive Java Applet

This applet is meant to show how efficient placement of guards on a convex terrain can be done. For simplicity, only vertex guards are considered here.

How to use the applet

For simplicity of representation, the terrains are displayed as a planar graph. Hence, interacting with the terrain takes place in two dimensions. Because all the properties used for guarding convex terrains also applies to this kind of graph, no information is lost.

The first step is to build the convex base of the terrain that you wish to work with. To do so, simply select the 'Build Base' button and place vertices on the plane. Only the convex hull is kept, so the final result is always convex.

Once the convex base has been built, you can stellate a face of the terrain and truncate a vertex, as detailed in the Problem section. To do so, simply select Stellate or Truncate from the menu. At the same time, you can also add guards at vertices using the Add Guards

Truncating is done the following way: given a vertex to be truncated, we construct a new vertex v' for each of its edges. v' is taken to be the midpoint of v and u, where (u,v) is an edge of v. We truncate the polyhedra through all these v'. Since we are using midpoints and not a set plane, this does not always result in clean behavior, but allows construction of most simple terrains.

Note that once the first stellation, truncation or guard placement occurs, no new vertices can be added to the convex base.

Restarting the applet can be done by simply selecting Restart from the menu. This will reset everything to its initial state.

To construct any graph, it is also possible to use the 'Graph Mode'. This will add disconnected nodes to the graph. Faces can then be constructed by selecting the chain of nodes for each face after selecting the 'Create Face' tool. For example, to build a three-sided pyramid-shaped terrain, first add three points in a triangle, then a fourth in their middle. Following this select the 'Create Face' tool, then click on two of the side points and the middle point, then click on the first selected point a second time. Repeating this for all faces will result in three faces being created. Note that using this method of constructing graphs it is very easy to construct graphs that have nothing to do with terrains. It is present to allow for construction of nicer-looking graphs and for faces with more than 3 vertices.

Using these simple tools, you should be able to get a feeling of how the terrains described on this website and in the paper can be constructed, as well as how they can be guarded.