WELCOME from Claude Duchesne and Ernesto Posse!

We constructed this Web site to present you our project for the course
**CS-507A Computational Geometry** at McGill University in Montréal.
We needed to choose a particular topic in Computational Geometry and expose
it on the Internet. The entire work is based on section 6.2 of the book
Art Gallery Theorems
and Algorithms by Joe O'Rourke.

The problem we choose is known as the **Fortress Problem**. Given
a fortress with "N" exterior sides, this problem asks to determine the
number of guards, watchmen or cameras needed to see its exterior. An "exterior
side" is defined as a straight part of the exterior wall. Unfortunately,
in Computational Geometry, fortresses and guards do not exist. These ancient
buildings are replaced by simple
polygons and the poor guards are simply replaced by points or crosses.
Fortunately, we will still call them "guards". In order for the guards
to see the entire exterior, there must be a non-intersecting segment that
links all the exterior points to at least one guard.

What is the minimum number of guards needed to see the exterior of a specific simple polygon? Where to place them exactly? Are there many equivalent ways to place the guards? These are good questions we could try to answer but they are not the ones we will answer here. We will not work on a specific simple polygon. Instead, we will be able to tell that for all simple polygons with "N" vertices, "X" guards are always sufficient and sometimes necessary. So, our problem is to find "X".

Figure 1 shows a typical middle age fortress viewed from above. The
simple polygon we talk about corresponds to the outside wall of the fortress.
We can forget all the other walls in the fortress. This figure also shows
two kinds of guards: the vertex guards (points) and the point guards (crosses).
A **vertex guard** is a guard that lies on a vertex of the polygon (on
one corner of the outside wall). A **point guard** is not restricted
to any location but it will logically not lie inside the polygon (because
he would not see any point of the exterior).

Figure 1 Example of a polygon and a fortress

The simple polygon (outside wall) in this example has 16 vertices, we
find easily that four vertex guards are necessary to see the entire exterior.
Intuitively, we could say that there is only one other possibility to place
four guards. Is it the case? In the same way, we see that four point guards
are necessary to see the entire exterior. But this time, there is an infinite
number of ways to place those four guards. What we expressed here explains
why we will study **two distinct cases: the use of vertex guards and point
guards**. You can take a look to these two separate problems using the
links in the navigation frame on the left.

The Fortress Problem was proposed independently by Derick Wood and Joseph Malkelvitch and is a variant of an older well-known problem: the Art Gallery Problem. The Art Gallery Problem asks the number of guards needed to see the interior of a polygon. Another variant is the Prison Yard Problem that is taking care of both the interior and the exterior (this last problem has not been satisfactorily solved).

Please, have fun on this interesting Web Site!

By Claude Duchesne and Ernesto Posse

McGill University (Claude and Ernesto) and École Polytechnique de Montréal (Claude)

October 1998

The Official Computational Geometry Web Page

Claude's Home Page

Ernesto's Home Page