The Fortress Problem


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.
Tower of London

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).

Example of polygon and fortress

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