Next: 2.5 Demands for Finite
Up: 2. Grid Types
Previous: 2.3 Grid Requirements
Subsections
2.4 Demands for the Box Integration Method
In association with the Box Integration discretization (refer Chapter 3, equations (3.32) and (3.57)), equation (2.10) can be rewritten as
where denotes a positive material parameter (the permittivity for the Laplace equation, for the diffusion equation). The parameters and are geometrical values which are determined by the geometry of the grid elements only.
is the length of the edge
between the points and (positive), and the coupling area between the two points.
As a geometrical consequence the coupling areas and point distances are symmetrical
and 
(2.12) 
and it is also of advantage and plausible to use a symmetrical material parameter

(2.13) 
which finally delivers a symmetrical system matrix
.
Consequentially, relation (2.11) is only satisfied if the coupling area is positive
However, such positive coupling areas are guaranteed by a Delaunay tessellation of the point set. In general, the definition of a Delaunay triangulation is based on the Voronoi diagram by the principle of duality [42] and will be introduced in the following section.
Let
be a finite set of points in a subdomain of the dimensional space
.
A Voronoi region is the set of all points of that are closer to than to any other point of
.

(2.15) 
The resulting Voronoi regions form a Voronoi tessellation of (without overlap or exclusion)

(2.16) 
By connecting the vertices , of two touching Voronoi regions and , a Delaunay edge
is constructed. The pool of all Delaunay edges builds the Delaunay mesh of the point set
.
This Delaunay graph shows the following properties:
Two points and form a Delaunay edge
if and only if there exists an dimensional sphere which passes and and contains no other points of
.
() Three noncollinear points , and form a Delaunay triangle
if and only if there exists an dimensional sphere which passes , and and contains no other points of
.
() Four noncoplanar points
, and form a Delaunay tetrahedron
if and only if there exists an dimensional sphere which passes
, and and contains no other points of
.
These formulations can be expressed in a mathematical way:
Here, is the center of the dimensional sphere. Analogous formulations can be found for Delaunay triangles and lines. A Delaunay tetrahedron implies that it must consist of Delaunay triangles and Delaunay edges.
Figure 2.3:
A twodimensional Voronoi box of the point

A twodimensional Voronoi box is shown in Figure 2.3.
In two dimensions the coupling area degenerates to the length of the Voronoi edge, which bisects the edge
and connects the two centerpoints of the outercircles of the triangles
and
.
By splitting this area into the parts and arising from the involved triangles
and
, respectively, the situation depicted in Figure 2.4(a) is obtained.
In this context, for each triangle
the possibilities shown in Figure 2.4(c) and Figure 2.4(d) exist.
The portion can lie inside or outside the half plane which is spanned by the straight line, built by and , and the point . By definition an insideportion is signed positive (Figure 2.4(c)) and signed negative if it lies outside (Figure 2.4(d)).
In consideration of nonoverlapping Voronoi boxes, the sum of both portions has to be positive.
And with geometrical considerations (refer Figure 2.4(b))
or equivalently,
has to be satisfied.
Figure 2.4:
A detail of the Voronoi Region shown before.
The components of the Voronoi regions of the triangles
and
.

The angle criterion for two dimensions. The marginal case with is reached if lies at the outercircle of
.

The center of the outercircle of the triangle
lies in the half plane
. The portion of the coupling area is positive
.

The center of the outercircle of the triangle
lies outside of the half plane
. The portion of the coupling area is negative
.


Figure 2.5:
Valid and invalid tessellations of two triangles.
Valid tessellation of two triangles,
and

Valid tessellation of the two triangles,
,
and in sum , a nonoverlapping Voronoi box remains

Invalid tessellation of the two triangles,
,
, but
, an overlapping Voronoi box remains

Invalid tessellation of the two triangles,
and
, also an overlapping Voronoi box is built


Consequently it follows that if the point lies inside the outercircle of the triangle
, relation (2.18) is violated. If lies outside or directly on the circle (marginal case), the relation is satisfied. This criterion must be fulfilled for each neighboring trianglepair of the mesh. Examples for valid and invalid (overlapping) twodimensional Voronoi edges are shown in Figure 2.5.
With other words:
There must not be any grid point, which lies inside the outercircle of each triangle.
This is known as the Delaunay criterion for two dimensions.
While the above criterion can be satisfied for each point set, for given geometry and boundary constrains the criterion must be formulated more strictly.
In that case, (2.14) must also be satisfied on the boundaries. The coupling area between two boundary points and must not be negative (see Figure 2.6). This means, all centers of the outercircles of the boundary triangles must lie within the boundaries. This type of triangulation is called a Constrained Delaunay Triangulation and the criterion can be formulated as:
There must not be any grid point, which lies inside the half circles constructed by the boundary lines.
Figure 2.6:
Valid and invalid Voronoi edges at the surface. At the marginal case, the center of the outercircle lies at the surface.
Valid triangulation at the boundary,

Invalid triangulation of the boundary,


2.4.3 ThreeDimensional Criterion
Figure 2.7:
The coupling areas of a threedimensional tetrahedral Delaunay grid around the point .
Typical Voronoi box around a grid point

Detail of the box, the coupling area between the point and

Viewing the coupling area along the edge

Separated situation


For the threedimensional case such an area is shown in Figure 2.7(b), which is based on a typical Voronoi box as shown in Figure 2.7(a). This area can be split into the different components due to each tetrahedron (shown in Figure 2.7(c) and the separated situation in Figure 2.7(d)).
The different parts are spanning triangles. Each triangle is defined by the center of the examined edge, the center of the outercircle of the appropriate triangle and the center of the outersphere of the tetrahedron.
Analogous to two dimensions, the sign of such an area of a box part that lies inside the tetrahedrons must be positive, outside areas have a negative sign, and generally, the areas are not allowed to overlap.
Figure 2.8:
The coupling areas between two points of different tetrahedrons.
Valid coupling area, the portions of both tetrahedrons are positive

Valid coupling area, one positive and one negative portion, in sum a positive, nonoverlapping area remains

Invalid coupling, one positive and one negative coupling portion, an overlapping area is constructed

Invalid coupling, both portions are negative, a negative and overlapping area remains


Such details of valid boxes are shown in Figure 2.8(a) and 2.8(b).
In the first example, both area parts are positive. In the second example, one area is negative, but smaller than the other one, which also leads to a valid grid.
Invalid details with a resulting negative sum of the areas are shown in Figure 2.8(c) and 2.8(d).
Such a tessellation of a point set is also a Delaunay tessellation and the criterion reads as follows:
There must not be any grid point, which lies inside the outersphere of each tetrahedron.

But different to the twodimensional case, no simplified angle criterion can be declared for three dimensions.
Also for threedimensional Delaunay grids, the coupling area between two boundary points and must not be negative. The threedimensional behavior is shown in Figure 2.9 and the criterion can be formulated:
There must not be any grid point, which lies inside the half spheres constructed by the boundary triangles.
Figure 2.9:
Valid and invalid Voronoi faces at the surface. At the marginal case, the center of the outersphere lies at the surface.
Valid surface triangulation, coupling areas at the surface are positive, the center of the outersphere of the tetrahedron lies inside

Invalid surface triangulation, negative coupling areas, the center of the outersphere of the tetrahedron lies outside


Next: 2.5 Demands for Finite
Up: 2. Grid Types
Previous: 2.3 Grid Requirements
J. Cervenka: ThreeDimensional Mesh Generation for Device and Process Simulation