## The Problem

Before looking at the problem itself, I will give a few important definitions
which are used in stating the problem.
### 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?