Civil Engineering Reference
In-Depth Information
350
Spiral_MG
Spiral_kd
300
250
Cluster_MG
200
Cluster_kd
150
100
50
0
4
8
12
16
20
Number of points (million)
Figure 8.64
CPU time for spiral and cluster distributions (20 million points).
number of points increased, as the time complexity of the kd-tree is of the order
O
(nlogn).
For the insertion of 20 million points, the construction of the kd-tree alone took 84.2 s,
which is already half of the total CPU time of 171.1 s for the regular grid insertion.
There is a great difference between regular grid insertion and multi-grid insertion for
points concentrated along a straight line, as shown in Table 8.11. The main cause for such a
large discrepancy is due to the time taken for the location of the BASE tetrahedron; NP for
regular grid was more than 200, and NP for multiple grid varied from 20 to 30, resulting in
a four-time difference in the insertion time. NP = 9 for kd-tree insertion is the smallest for
the three insertion schemes. However, the NR value of the kd-tree is double of that of the
regular grid insertion or the multi-grid insertion, resulting in only a slightly more efficient
insertion scheme overall. However, if the grid construction time is also taken into consid-
eration, the total CPU time of the kd-tree scheme is just about the same compared to the
multi-grid insertion scheme.
The diagonal distribution was the first major challenge for the various insertion schemes.
With a similar NR value, NP = 150 of the regular grid insertion is much higher than NP = 25
of the multi-grid insertion, leading to about a three-time difference in the overall perfor-
mance. As for the kd-tree insertion, with an NP value of 9.5 and an NR value of 35, exclud-
ing the grid construction time, the insertion time is slightly less than that of the multi-grid
insertion for the insertion of 20 million points.
As points are fairly evenly spread over the ellipsoidal surface, the performance of the three
insertion schemes is roughly the same for the ellipse distribution. It is interesting to note that
the CPU time taken for the ellipse distribution is even less than that of the uniform random
distribution for the insertion of 0.4 to 20 million points. A possible cause for this to happen
is that perhaps the average number of points in a cell for the ellipse distribution is closer to
the optimal number of insertion (15-30) compared to the case of the uniform distribution
in which the specified number of points in a cell had been set equal to 8.
The spiral distribution was another difficult case for various point insertion schemes. The
NP value of 160 for the regular insertion is much higher compared to that of the uniform
distribution, resulting in a three-time increase in the CPU time for the insertion of 2 million
points. With reference to the uniform distribution, the NP values for multi-grid insertion
increased only slightly from 7.5 to 20, resulting in a slight increase in the CPU time from
170 to 237 s for the insertion of 20 million points. Although there is not much difference
in the overall performance of the kd-tree insertion with a small NP value of 10 and a large
