Surveilling roads and protecting art

Placing security cameras in buildings, finding good locations for cameras to enforce speed limits or placing guards to defend a border are some of the problems we face everyday. A nation that wishes to defend its border with armed guards wants to be sure the entire border is secure. However, hiring more guards than necessary can be costly. A start-up company moving into a new building wants to be sure every room in the building is seen by some security camera. Cameras are expensive and the company wants to install the smallest number of cameras; at the same time the company wants to be sure the building is secure.

These problems, and many other visibility type problems, are not easy to solve in general. In some specific cases, optimal solutions can be obtained quickly. In general, finding an optimal solution may take a very long time.

The original results of this thesis address some of these problems. We show some positive results for solving some of these visibility problems. We also give some negative results for some of these problems. These negative results are useful because they tell us that we are unlikely to find a fast algorithm to solve a particular problem optimally.