Civil Engineering Reference
In-Depth Information
points for setting up the initial triangulation are not placed to infinity. It is very close to a
convex hull, except that some boundary edges of the point set may be missing. However,
results generated by parallel point insertion have all been checked against those produced by
the sequential point insertion by one processor.
7.3.6 Efficiency analysis
As the zonal point insertion is completely independent, the algorithm is expected to be very
efficient and 100% scalable depending only on the characteristics of zonal partition. The
extent of zonal boundary depends on how cells are partitioned into zones, and usually, the
zonal boundary will increase with the number of zones. Let's consider various schemes of
the partition of a unit square into zones for parallel point insertion by four processors, as
shown in Figure 7.12. From a simple boundary count, a four-zone partition (2 × 2) will
be the most efficient with a boundary of 8 units, whereas a 4 × 1 strip division will have a
common boundary of 10 units and the least efficient 2 × 4 division will create a common
boundary of 12 units.
For a k × k division into zones, the number of internal boundary cuts is given by
cuts = 2(k − 1)
Suppose that m is the average number of layers of cells added to each side of a cut line to
achieve convergence for boundary Delaunay triangles; then the increase in the workload μ
in triangulating the zones is given by
NN
+− +
21
(
kmNN
NN
)
(
)
xy
x
y
=
xy
where N
x
and N
y
are, respectively, the number of cell divisions along the x- and y-axes.
For a square domain with equal zonal division on each side (N
x
= N
y
), we have
=+
−
41
(
km
N
)
(
N
4(k)
−
1
)
x
1
m
=
−
1
x
A numerical experiment has been carried out to triangulate 10 million 2D points using
various zonal divisions. Setting n = 16, N
x
= N
y
= 791, and the results are shown in Table 7.1.
In terms of redundant triangles generated, as predicted, m is more or less a constant,
and it varies only very slightly from 1.10 to 1.16 for zonal divisions 2 × 2, 3 × 3 to 8 × 8.
Boundary = 4 + 2 × 2 = 8
Boundary = 4 + 2 × 3 = 10 Boundary = 4 + 2 × 4 = 12
Figure 7.12
Partitioning a square into zones.
