Civil Engineering Reference
In-Depth Information
Figure 7.21
Partition of tetrahedra into eight zones by the minimum vertex scheme.
Over each zone, all the tetrahedra generated will be examined and allocated with the
minimum vertex allocation scheme simultaneously by all the processors. At the end of a
single pass by all the processors, tetrahedra will be partitioned into zones, and redundant
tetrahedra are all eliminated as each tetrahedron should belong to one and only one zone. By
the minimum vertex allocation, redundant tetrahedra for the parallel insertion of 2000 spa-
tial points are eliminated and distributed into eight zones, as shown in Figure 7.21. Strictly
speaking, this is not the convex hull of the given points but a DT of the points with some
missing tetrahedra on the boundary surface.
7.4.5 Zonal insertion is Delaunay and complete
We have to assure that the zonal insertion algorithm produces Delaunay triangulation and
the Delaunay tetrahedra around each point exist for any point in the zone. Let
S
be the set of
points in zone
Z
under consideration. Let
I
be the set of interior tetrahedra in zone
Z
, where
an interior tetrahedron of
Z
is a tetrahedron with all its four vertices taken from
S
. Let
B
be the set of boundary tetrahedra of
Z
, where a boundary tetrahedron of
Z
is a tetrahedron
with vertex or vertices taken from
S
and vertex or vertices from the neighbouring zone(s).
Hence, the triangulation
T
constructed in the zonal insertion process consists of tetrahedra
from
I
and
B
, i.e.
T
=
I
∪
B
(I)
T
is Delaunay. Let α and β be two adjacent tetrahedra of
T
,
α
∈
T
⇒
α
∈
I
∪
B
, β ∈
T
⇒
β ∈
I
∪
B
i.
α ∈
I
and β ∈
I
. In the insertion process, the vertices of α and β are taken from
S
.
Hence, by construction, α and β are mutually exclusive, which means that the cir-
cumsphere of α does not contain any vertex of β in its interior and vice versa.
