DOI

10.17077/etd.5fmc560l

Document Type

Dissertation

Date of Degree

Fall 2009

Degree Name

PhD (Doctor of Philosophy)

Degree In

Computer Science

First Advisor

Varadarajan, Kasturi

First Committee Member

Pemmaraju, Sriram

Second Committee Member

Bruell, Steve

Third Committee Member

Hourcade, Juan Pablo

Fourth Committee Member

Jay, Laurent

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

Download

Share

COinS