Civil Engineering Reference
In-Depth Information
Table 7.1
Estimate number of additional layers for convergence
Zones NT NE N
x
μ
=NT/NE m
2 × 2 20,107,826 19,995,274 791 1.00563 1.11
3 × 3 20,216,146 19,995,274 791 1.011 1.10
4 × 4 20,330,252 19,995,274 791 1.017 1.12
5 × 5 20,445,806 19,995,274 791 1.023 1.14
6 × 6 20,564,566 19,995,274 791 1.028 1.11
7 × 7 20,690,300 19,995,274 791 1.035 1.15
8 × 8 20,816,146 19,995,274 791 1.041 1.16
Note: NT and NE are the number of triangles generated and in the convex
hull, respectively.
However, in terms of CPU time, the result is quite different, and various zonal divisions
almost take the same CPU time for point insertion by a single processor tested on PC, as
shown in Figure 7.13. The analysis of point insertion by multiple processors will be deferred
to Section 7.3.8 as maximum efficiency can only be attained when the number of zones N
c
is an integral multiple of the number of processors employed. The almost constant CPU
time for different zonal divisions is a very intriguing phenomenon. As mentioned before, the
speed of DT by point insertion is rather sensitive to the order of points inserted, and usually,
points inserted in clusters in a contiguous manner would be more efficient than a random
insertion following the natural order of the points. A finer zone division will generate more
redundant triangles on the common boundary, as shown in Table 7.1. However, point inser-
tion clustered within a smaller zone is likely to be more efficient than the insertion in a larger
zone. The extra workload in generating more redundant triangles is just offset by the slightly
higher efficiency in DT over a smaller zone.
In fact, in point insertion without zonal division, if points are inserted following the natural
order, a complexity of
O
(N
2
) is resulted for a set of N points, and the scalability is well over
100%. Of course, this is not reasonable but is a by-product of points being sorted into cells
and inserted following the cell adjacency order. In a point insertion without zonal division, if
points are sorted into cells that are then inserted following the cell adjacency order, a linear
time complexity is achieved, but it is still slightly slower than a serial insertion with zonal
90
80
70
60
Single zone
2 × 2
3 × 3
4 × 4
5 × 5
6 × 6
7 × 7
8 × 8
16 × 16
50
40
30
20
10
0
10
20
30
40
50
Number of points in million, N
Figure 7.13
Zonal point insertion by a single processor.
