2004
tellite
with
es of
art 7,
Deep
ca, 94
MULTIPLE OBSERVER SITING ON TERRAIN WITH INTERVISIBILITY OR LO-RES DATA
W. Randolph Franklin & Christian Vogt
Rensselaer Polytechnic Institute, Troy, New York, USA 12180-3590
http://Www.ecse.rpi.edu/Homepages/wrf/
KEY WORDS: Cartography, GIS, Mapping, Land, Vision, Analysis, Resolution, Terrestrial
ABSTRACT
We describe two current projects with our toolkit for siting multiple observers on terrain. (Both observers and targets are
at some specified height above ground level. Observers can see targets, when not hidden by the terrain, out to a specified
radius of interest.) Siting the observers so that they are intervisible, i.e., so that the visibility graph is a connected set, is
the first project. The second project tests the effect, on the optimality of the multiple observer siting (w/o intervisiblity),
of reducing the map cell's horizontal or vertical resolution. We lowered the resolution, sited observers optimally, then
computed those observers' joint visibility index on the hi-res data. We observed that much less precise vertical resolution
is ok, but that reducing the horizontal resolution by even a factor of two leads to an observer siting with significantly
reduced joint visibility index, when evaluated on the hi-res data. Applications of multiple observer siting include siting
radio towers and mitigating visual nuisances.
1 INTRODUCTION
The results reported here are part of our extended project
that might be called Geospatial Mathematics, to under-
stand and process terrain data, which means elevations
in this context. Previous results have included e a Trian-
gulated Irregular Network (TIN) program that can com-
pletely and quickly tin a 1201 x 1201 level-1 USGS DEM,
(Franklin, 1973, 2001; Pedrini, 2000), e Lossy and loss-
less compression of gridded elevation databases, (Franklin
and Said, 1996), e Interpolation from contours to an eleva-
tion grid, (Childs, 2003; Gousie and Franklin, 1998, 2003;
Gousie, 1998), and e a siting toolkit for Viewshed and vis-
ibility index determination, (Franklin, 2002; Ray, 1994).
Current components of this effort include researching new,
compact, terrain representations, such as a “scooping”
operator, and approximation from known points with an
overdetermined Laplacian PDE. We are also studying op-
erations on terrain, such as lossy compression while main-
taining important properties, including gradients and visi-
bility.
For visibility, this project has moved beyond viewshed and
visibility indexes to study their applications, such as mul-
tiple observer siting, and limitations caused by finite hor-
izontal or vertical resolution. This paper extends our ear-
lier visibility work, including our siting toolkit, described
in Franklin (2000, 2004a,b) and Franklin and Ray (1994),
which also survey the terrain visibility literature. Notable
related research includes the analysis of the effect of ter-
rain errors on the computed viewshed in Nackaerts et al.
(1999) and Fisher (1992), and the relation of visibility to
topographic features studied in Lee (1992), and the pi-
oneering work of Nagy (1994). Line-of-Sight Technical
Working Group (2004) compared various LOS algorithms.
Caldwell et al. (2003) computed a complete intervisibil-
ity database, the viewshed of every point in a 466 x 336
DEM. Champion and Lavery (2002) studied line-of-sight
on natural terrain defined by an L,-spline.
Consider a terrain elevation database (map cell), and an
observer, O. Define the viewshed as the specific terrain
visible from O that lies within some radius of interest, R,
of O. The observer might be situated at a certain height, 71,
above ground level, and might also be looking for targets,
7, also at height H above the local ground. Note that if
the observer and target heights are different then visibility
is not symmetric.
Since the line of sight from O to 7 generally falls between
adjacent elevation posts, some interpolation rule is nec-
essary. Small changes in the interpolation rule can cause
large changes in the computed viewshed. That subject still
requires research since the correct choice depends on the
assumed terrain model. Assuming terrain to be C® (ie.
its derivatives of every order are continuous), is false. In-
deed among the most important terrain features are cliffs,
which are discontinuous. However, some assumption has
to be made.
Define the visibility index of O as the fraction of the points
within R of O that are visible from O. The single observer
siting problem is to site (i.e., find the location of) O so as to
maximize its visibility index. The multiple observer siting
problem is to site a set of observers so as to maximize their
joint visibility index, i.e., the area of the union of their indi-
vidual visibility indexes. We may find either the minimum
number of observers to cover a specified area, or else the
maximum area covered by a given number of observers.
Covering all the terrain is probably impractical because of
isolated single points that are lower than all their neigh-
bors, and so are hidden from distant observers.
This multiple observer case is particularly interesting and
complex, and has many applications. A cell phone
provider wishes to install multiple towers so that at least
one tower is visible (in a radio sense) from every place
a customer's cellphone might be. Here, the identities of
the observers of highest visibility index are of more inter-
est than their exact visibility indices, or than the visibility
indices of all observers. One novel future application of
siting radio transmitters will occur when the moon is set-
tled. The moon has no ionosphere to reflect signals, and no
stable satellite orbits. The choices for long-range commu-
nication would seem to include either a lot of fiber optic
1197
