pointer from any list element that stores a point of P to the corresponding node
in 7-. Otherwise we may not be able to locate the points of which the error has
changed efficiently in 7-. These pointers are shown as solid lines with arrows in
Figure 8. The pointers from the triangle records to the lists are shown dotted.
If k is the number of neighbors of p in DT(S U {p}), then k - 2 triangles
were destroyed and k new ones were made. Let m be the number of points in the
triangles incident to p in DT(SU{p}). Then the iteration that added p as a vertex
of the TIN requires O(k + log n) time for updating the Delaunay triangulation,
O(km)
time to redistribute the m points over the k triangles, and
O(klogn)
time to update the balanced binary tree 7-. In the worst case, rn and k are both
linear in n, giving an worst case performance of O(n3). But redistribution of the
points can also be done in O(k + m log m) time by sorting the m points by angle
around p. Since all new triangles in the TIN are incident to p, we can distribute
the m points over the k triangles by using the sorted order. The modification
improves the worst case running time to O(n 2 log n).
One can expect that k is usually constant, and after a couple of iterations
of the algorithm, m will probably be much smaller than n. The more iterations,
the smaller m tends to be. One can expect that the algorithm behaves more
like the best case than like the worst case, for typical inputs. In the best case,
k will be constant, and every list of points stored with a triangle reduces in
length considerably each time it is involved in a redistribution.. This means that
later iterations in the algorithm go faster and faster, since m decreases from
linear in n to a constant. If k is assumed to be a constant, we needn't use the
modification to distribute the points, but simply spend O(km) = O(m) time.
Using an amortized analysis technique, one can show that the whole algorithm
will take O(n log n) time under the assumptions given.
4.3 From Contour Line to TIN
Contour line to TIN conversion algorithms are useful because elevation data is
often obtained by digitizing contour line maps. A contour line map is already
a vector data structure, in fact, a planar subdivision where the vertices and
lines are assigned the elevation of the contour line they are on. To convert the
contour lines to a TIN, the obvious thing to do is triangulate all regions, that is,
triangulate between the contour lines. Each region can be seen as a polygon with
holes, and there are standard triangulation algorithms known for this problem
in computational geometry [t8, 91, 98].
Instead of using any triangulation it is a good idea to use one that gives nicely
shaped triangles, like the Delaunay triangulation. However, the input to the
triangulation algorithm is a polygon, not a point set. There exists a triangulation
that follows the Delaunay triangulation as closely as possible, given some given
set of edges must be present. It is called the constrained Delaunay triangulation
[9, 22].
In the GIS literature, a couple of approaches to triangulate between contour
lines have been described [10, 28, 47, 102]. One of the problems with the con-
strained Detaunay triangulation and some of the other methods is that they may
52