Visibility

Throughout this text on website points are assumed to be in general position, that no point has a negative z coordinate (this is done without loss of generality, since we can simply translate the polyhedra), and that the surface is triangulated. Furthermore the polyhedra discussed are assumed to be so that for any vertical line intersects the surface in only one point. Following these assumptions we can derive that if we project a terrain T (the triangulated surface) is a planar graph with no crossing edges.

We say that a point p is visible from a if we can draw a straight line from a to p without intersecting with the surface. Also, p is said to be visible from an edge e if we can find a point on e such that p is visible from this point.

Finally, a terrain is considered covered by a set of guards if "every point on the terrain is visible from at least one guard in the set." [1]

Convex Terrains

A terrain T is defined to be convex if every point on T is also a point on the boundary of the convex hull of the vertices of T.

There are two main operations used in the lower bounds proofs that relate to the terrains.

• Truncation: Operation that removes a vertex V from T, where T is a convex terrain, and preserves its convexity. It does so by removing the faces connected to V and adding a face connected to all the vertices that V was connected to.
• Stellation: Operation that adds a vertex V to T, where T is a convex terrain, and preserves its convexity. This is the inverse operation of truncation.

The Problem

The problem discussed in [1] is as follows: what is the minimum number of guards placed at vertices of a terrain T that we might need to cover T. Similarly, if we consider edge guards such that an edge guard G sees a point p if p is visible from that edge, then what is the minimum number of edge guards that we might need to cover T?