Border PatrolShingo MurataSwarthmore CollegeSwarthmore, [email protected] AmatoSwarthmore CollegeSwarthmore, [email protected] implement a border patrol programthat computes ideal locations for observa-tion towers overlooking a border of inter-est. In this particular project, we studythe border of Arizona facing Mexico. Weuse GRASS to manipulate elevation rasterdata. Our algorithm extracts the borderfrom a raster file and locates candidate po-sitions for observation towers along thatborder. The viewshed of each observa-tion tower is computed with a direct line ofsight algorithm. We employ a tower place-ment algorithm to select only the neces-sary towers from the set of all candidatetowers. Our algorithm selected 92 towerswithin a 5km zone from the border to pa-trol the approximately 680km border.1 IntroductionBorder patrol is a common interest involved in na-tional security. Militaries are frequently concernedwith detecting threats along the extent of a particularborder as completely and efficiently as possible. Itis important that border security can be establishedcost-effectively as well. We model this problem asthe task of placing the minimum number of towersnecessary to view the entire border of interest withinsome range of that border.Current GIS technology makes it possible to au-tomate the process of planning optimal locations forborder observation towers. In this paper we developalgorithms to automatically extract a border from araster file, find candidate tower locations near theborder, and select the optimal set of towers that iscapable of observing the entire border.Elevation data for many areas of interest are read-ily available on the Internet. We use the GeographicResources Analysis Support System (GRASS) fordata manipulation. GRASS is suited for this projectbecause it has full functionality in visualizing eleva-tion, data conversion, and I/O support for ascii filesthat are compatible with our C programs. With anabundance of digital elevation models in raster for-mat and the software tools to manipulate them, wecan successfully apply useful viewshed computationalgorithms to the problem of finding the optimal setof observation towers.The viewshed of a view point is the set of pointsin the terrain model that can be observed from thatpoint. Viewshed computation is central to the au-tomation of these algorithms because it is essentialto know which border points a candidate tower is ca-pable of observing. Our tower placement algorithminvolves the iterative selection of candidate towerswith the greatest contribution of yet unseen borderpoints to the current optimal set of observation tow-ers.There are several parameters involved in towerplacement. One of our goals is to minimize the num-ber of towers we need to observe the entire border.This number is dependant both on the height of thetowers and the maximum distance they are allowedto be placed from the border. As the height of thetowers is increased, the number of necessary tow-ers decreases, but the cost of each tower increases.Finding a cost-minimizing solution would involvebalancing these factors. Increasing the distance fromthe border in which towers can be placed may incor-porate useful elevation maxima into the model thatwere previously out of range. The gains from thisare limited by atmospheric conditions that limit vis-ibility and, ultimately, by the curvature of the Earth.We begin by reviewing the viewshed algorithmpresented by David Izraelevitz in (Izraelevitz, 2003).We then describe in detail the three major steps inour project: border extraction, viewshed computa-tion, and tower placement. Finally, we present theresults in section 4.2 Related WorkSeveral algorithms for computing the viewshed ofa point are presented in (Izraelevitz, 2003). Thefirst method presented is direct computation. Thismethod essentially checks each possible obstructionon a line from the view point to the target point. Ifthere are no obstructions along this line, then the tar-get point is considered visible. This algorithm isstraight forward, but is computationally inefficient,because it requires O(n) computations for each gridpoint on an n x n field, resulting in an O(n3) algo-rithm.The Xdraw algorithm employs the Line of Sight(LOS) function to compute the viewshed of a viewpoint. This algorithm is faster than the direct methodbecause it stores previous results that can be utilizedat the next stage of computation along the same line.The final algorithm improves the Xdraw algo-rithm by introducing a backtracking method to re-duce the number of interpolations and increase theaccuracy of the LOS calculations. If any point alongthe line between the view point and the target pointcoincides with a grid data point, that data point isused to initialize the LOS computation. Otherwise,the algorithm backtracks a specified distance andinitializes the computation with an interpolated LOSvalue.To determine border visibility, we do not needto compute the entire viewshed from a given viewpoint. We only need to determine whether targetpoints on the border are visible from a tower’s viewpoint. It is irrelevant to know whether the points be-tween the observation tower and the border are vis-ible. This negates the benefits of the Xdraw algo-rithm which are based on a fast incremental compu-tation. We implement and use the direct algorithmbecause its inefficient computation is mitigated dueto the limited number of points we are examining.In addition, its accuracy is superior to Xdraw.Vincent presents an alternative viewshed algo-rithm based on ray casting in three dimensionalpolygonal models in (Vincent, 1999). The algorithmis based on a hierarchical partitioning of three di-mensional space. This partition is represented by ak-d tree. The hierarchical partitioning of the spacecontinues until the model of the terrain is enclosedin appropriate bounding boxes. This hierarchicalstructuring of the space allows Vincent to increasethe search speed for view obstructions. Other opti-mizations include a backface culling mechanism toremove irrelevant surface polygons from the searchspace and a parallelization of the algorithm. Vincentalso sets up an error vs. speed tradeoff by adaptivelyspacing the rays used to test for intersection. As thenumber of rays increases, accuracy improves at thecost of increased execution time.3 MethodsOur automated border patrol algorithm has threemain phases. First, the relevant border must