tofn 
li v2, 
at the 
iangle 
xactly 
ly the 
f the 
e., no 
to the 
ulated 
can be 
ship: 
ndary 
cribed 
ertices 
lation. 
or, the 
tegers 
ng the 
it will 
em of 
'onvex 
there 
which 
  
  
p4 p2 
tl 
p3 
pl 
p4 p2 
2 
p3 
Figure 1: Triangulation of four points 
A number of different criteria have been invented 
for choosing between t4 and to. The simplest one is 
to let p, ..., p4; be oriented as in Figure 1, and let 
d, = length of the diagonal pap4, and da = length of 
the diagonal P,Pg. Then t9 is a better 
triangulation of t4 with respect to the shortest 
diagonal criterion which provided that d, > da. 
Although it is very easy to implement, the shortest 
diagonal criterion does not do a good job of 
avoiding thin triangle. The following max-min 
angle criterion contributed by Lawson (1977) is 
specially designed to avoid thin triangle. If there 
is a triangle t, let a(t) = minimum angle in t. 
Associated with the triangulation T, let a(T) = min 
{a(t): te T}. Then to is better than t4 with respect 
to the max-min angle criterion which provided 
that a(t5) » a(t4). In Figure 1, a(t4) - 30? while alta) 
- 469, and thus according to the max-min angle 
criterion, triangulation to is the better of the two. 
Although the error in approximating a smooth 
function on a triangle can be estimated in terms of 
the largest angle in the triangle, Barnhill and 
Little (1984) suggest the following min-max angle 
alternative to the max-min angle criterion: if 
there is a triangle t, let a(t) = 1/(maximum angle 
in t). Associated with the triangulation T, let a(T) 
- min ( a(t) : t e T ). Then ty is a better 
triangulation than t4 with respect to the min-max 
angle criterion which provided that a(to) » a(t4). 
Regarding the optimal triangulations of general 
points sets, let Q be a criterion for choosing the 
optimal triangulation of a quadrilateral based on 
maximizing some measure a(t) of the thinness of 
the triangles. For each triangulation T of a point 
set P, let a(t) be the vector measure of goodness of 
T defined above. Then a triangulation tq is said to 
be an optimal triangulation of P with respect to Q 
provided that a(tg) > a(ty) for all other 
triangulations t; of P. 
929 
Post optimized, iteratively built, and divide-and- 
conquer approaches are three rather different 
algorithms which can be adopted to work with the 
above swap criteria for constructing the optimal 
triangulations. The post optimized approach first 
constructs an initial triangulation, and then goes 
through the quadrilaterals and makes swaps 
where necessary. The iteratively built approach 
starts with one triangle and adds one point at a 
time, making sure that at each step the current 
triangulation is locally optimal. The divide-and- 
conquer approach divides the data up into pieces, 
finds locally optimal triangulations for each piece, 
and then merges these triangulations. Every 
triangulation approach requires at least nlog(n) 
operations (Lawson, 1977), where n is the number 
of points being triangulated. 
3. GRADIENT ESTIMATION 
Many techniques for producing a surface from 
scattered DEM require gradients at the data 
points. Typically, only positional data are known 
so the gradients must be estimated before the 
surface values can be computed. The quality of the 
surface depends on the estimated gradients so it is 
important to compute accurate estimates. For the 
planar interpolation problem, there are five 
common gradient estimation methods: Shepard, 
multiquadric, weighted quadric, weighted planar, 
and triangular Shepard methods. The Shepard 
method which interpolates only to positional data 
is defined by 
  
n 
GS(x, y) - >, wi, y) Fi (x, y) (1) 
i=l 
where 
n 
dj", y) 
zi 
wi y) = 
Y II dj ^x, y) 
k=1j#k 
and 
dj", y) » (x -xJ* « y - 59° 
GS(x, y) was localized in the following way. For 
each (x, yj), GS is determined by the six data 
points closest to (x;, y;). Note that (x;, y;) has to be 
excluded from the computations; otherwise, the 
gradients at (xi, yj) would be zero.