Civil Engineering Reference
In-Depth Information
processor can be assigned to each point for the maximum speed-up. Nevertheless, machines
with so many processors are not yet available, and even if they exist, it may not be economi-
cal to have so many processors working together as conflicts are bound to occur for the
insertion of neighbouring points.
7.2.2 The zonal insertion scheme
Realising that the point insertion scheme is a very efficient algorithm for well-organised
points as only a few operations are involved for each point insertion, any additional tests,
control or single-processor operations will substantially slow down the overall rate of the
parallel insertion process. For example, in a parallel insertion process, if the number of
operations in locating the base triangle and in the verification of the circumsphere criterion
has to be doubled, the efficiency will drop by 50%. Hence, the basic operations for point
insertion should remain more or less the same when there are several processors working
together.
Let's start from the ideal situation in which one processor is assigned to each point for
simultaneous insertion. We have to ensure that each triangle connected to the inserted point
p
is Delaunay, and the simplest check to assure this is to apply the circumcircle criterion
that each triangle connected to
p
contains no point in its interior, as shown in Figure 7.2.
An effective means to achieve this is to make use of some spatial control on the points,
and a partition of points into zones could well serve this purpose. As shown in Figure 7.2,
the patch of triangles associated with point
p
is Delaunay if no point exists in the union of
circumcircles passing through point
p
, or if there is no point in the box bounding all the
circumcircles of
p
. For an efficient insertion of a large set of points, points are already sorted
into cells, and to check whether the bounding box contains any other points will just be a
simple task.
It is impractical and unnecessary to assign one processor to each point as there is a lot
of redundancy in doing so, and an optimised scheme is to group several cells together into
a zone for a single-processor insertion. As a result, cells are grouped into a number of
zones depending on the number of processors available. There are two major issues to be
addressed in such a scenario: (i) how to make sure that Delaunay triangles are generated
between zones and (ii) how to get rid of the redundant elements efficiently on the boundary
between zones.
p
Figure 7.2
Patch of Delaunay triangles.
