Document Type
Dissertation
Date of Degree
Fall 2009
Degree Name
PhD (Doctor of Philosophy)
Degree In
Computer Science
First Advisor
Kasturi Varadarajan
First Committee Member
Sriram Pemmaraju
Second Committee Member
Steve Bruell
Third Committee Member
Juan Pablo Hourcade
Fourth Committee Member
Laurent Jay
Abstract
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.
Keywords
algorithms, complexity, geometry, set cover, terrain, theory
Pages
x, 114 pages
Bibliography
Includes bibliographical references (pages 111-114).
Copyright
Copyright 2009 Erik Allyn Krohn