Date of Award


Document Type


Degree Name

Master of Science


Department of Operational Sciences

First Advisor

Karen Dillard, PhD.


Air surveillance of United States territory is an essential Department of Defense function. In the event of an incoming aerial attack on North America, the DoD, Department of Homeland Security, and Federal Aviation Administration surveillance capabilities are critical to discovering and tracking the threat so that it can be eliminated. Many of the currently used surveillance radar will reach the end of their design life within ten to twenty years. By replacing the current radar network with a single integrated network of Multifunction Phased Array Radar (MPAR) units, surveillance capabilities can be enhanced and life cycle cost can be reduced. The problem of determining the location of required MPAR units to provide sufficient air surveillance of a given area is a large problem that could require a prohibitively long time to solve. By representing the area of surveillance as a polygon and the MPAR units as guards with a defined circle of detection, this problem as well as similar surveillance or coverage problems can be expressed with easily adjustable parameters. The problem of covering the interior and exterior of a polygon region with a minimal number of guards with homogeneous capabilities is not well researched. There are no methods for determining the minimal number of guards required to cover the interior and exterior of a polygon at a desired coverage level less than 100 percent. This paper describes an iterative method for determining a small number and location of guards required to cover a convex polygon both fully and at a specified percentage coverage less than 100 percent. Results are presented to show that the developed methodology produces a smaller number of required MPAR units using less time than a comparable method presented in the literature. A goodness measure of the method is presented with respect to a lower bound for over 1000 test cases. Results for the United States Northern Command MPAR instance of this problem are presented to provide full and partial coverage of the Continental United States and 25 key cities of interest. The methodology developed in this thesis can be used to provide minimal cost surveillance recommendations over key areas or events, placement of communications resources, or other limited range resources

AFIT Designator


DTIC Accession Number