Civil Engineering Reference
In-Depth Information
Table 7.5
Insertion by 4 × 4 zonal division
Processors
CPU time
Speed-up
Efficiency
1
27.2
1.00
100
2
14.92
1.82
91
4
7.57
3.59
90
6
5.74
4.74
79
8
3.84
7.08
89
120
100
80
CPU time
Speed-up
E
ciency
60
40
20
0
1
2
4
6
8
Number of processors
Figure 7.16
Parallel Delaunay triangulation using 4 × 4 zones.
and efficiency is given in Figure 7.16. It can be seen that parallel insertion at high efficiency
of 90% was achieved using two, four or eight processors, whereas the efficiency dropped by
more than 10% when six processors were used.
7.4 PARALLEL DELAUNAY TRIANGULATION IN 3D
The parallelisation algorithm presented in Section 7.3 for Delaunay point insertion in 2D is
a generic scheme, which can be readily extended in higher dimensions. Nothing needs to be
changed in the concept or in the procedure moving from a 2D setting to a 3D one, except
for some natural modifications such as 2D plane to 3D space, (x, y) co-ordinates to (x, y, z)
co-ordinates, triangles to tetrahedra, circles to spheres, etc.
7.4.1 Points partitioned into cells
Let N be the number of points in a 3D Delaunay triangulation, and n be the average number
of points desirable in a cell. Then
nN
x
N
y
N
z
= N
(7.2)
where N
x
, N
y
and N
z
are, respectively, the number of cell divisions along the x-, y- and
z-axes, and the number of cells N
c
= N
x
N
y
N
z
.
Let x
min
, x
max
, y
min
, y
max
, z
min
, z
max
be the bounds of the (x, y, z) co-ordinates of the point
set; compute R
x
= x
max
- x
min
, R
y
= y
max
- y
min
and R
z
= z
max
- z
min
, and then N
x
, N
y
and N
z
can be determined by substituting λR
x
= N
x
, λR
y
= N
y
and λR
z
= N
z
into Equation 7.2.
