next up previous contents
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

$\displaystyle s_{ij} = - f_{ij} \;\frac{A_{ij}}{d_{ij}} \leq 0,$ (2.11)

where $ f_{ij}$ denotes a positive material parameter (the permittivity for the Laplace equation, $ 1$ for the diffusion equation). The parameters $ d_{ij}$ and $ A_{ij}$ are geometrical values which are determined by the geometry of the grid elements only. $ d_{ij}$ is the length of the edge $ < p_ip_j >$ between the points $ p_i$ and $ p_j$ (positive), and $ A_{ij}$ the coupling area between the two points. As a geometrical consequence the coupling areas and point distances are symmetrical

$\displaystyle A_{ij}=A_{ji}$   and$\displaystyle \qquad d_{ij}=d_{ji},$ (2.12)

and it is also of advantage and plausible to use a symmetrical material parameter

$\displaystyle f_{ij}=f_{ji},$ (2.13)

which finally delivers a symmetrical system matrix $ {\mathrm{\bf S}}$. Consequentially, relation (2.11) is only satisfied if the coupling area is positive

$\displaystyle A_{ij} \geq 0.$ (2.14)

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.

2.4.1 Voronoi Tessellation -- Delaunay Mesh

Let $ \mathcal{P}=\{p_1,p_2,\ldots,p_r\}$ be a finite set of points in a sub-domain $ \Omega^n$ of the $ n$-dimensional space $ \mathcal{R}^n$.

A Voronoi region $ V(p_i)$ is the set of all points of $ \Omega^n$ that are closer to $ p_i$ than to any other point of $ \mathcal{P}$.

$\displaystyle V(p_i)=\{p\;\vert\;p \in \Omega^n \;\wedge\; \vert\vert p - p_i\vert\vert<\vert\vert p-p_j\vert\vert, \;\forall\; j \neq i\}$ (2.15)

The resulting Voronoi regions $ V(p_i)$ form a Voronoi tessellation of $ \Omega^n$ (without overlap or exclusion)

$\displaystyle \Omega^n=\bigcup_{i=1}^r V(p_i).$ (2.16)

By connecting the vertices $ p_i$, $ p_j$ of two touching Voronoi regions $ V(p_i)$ and $ V(p_j)$, a Delaunay edge $ < p_ip_j >$ is constructed. The pool of all Delaunay edges builds the Delaunay mesh of the point set $ \mathcal{P}$. This Delaunay graph shows the following properties:

Two points $ p_i$ and $ p_j$ form a Delaunay edge $ < p_ip_j >$ if and only if there exists an $ n$-dimensional sphere which passes $ p_i$ and $ p_j$ and contains no other points of $ \mathcal{P}$.

($ n \geq 2$) Three non-collinear points $ p_i,p_j$, and $ p_k$ form a Delaunay triangle $ < p_ip_jp_k >$ if and only if there exists an $ n$-dimensional sphere which passes $ p_i,p_j$, and $ p_k$ and contains no other points of $ \mathcal{P}$.

($ n \geq 3$) Four non-coplanar points $ p_i,p_j,p_k$, and $ p_l$ form a Delaunay tetrahedron $ < p_ip_jp_kp_l >$ if and only if there exists an $ n$-dimensional sphere which passes $ p_i,p_j,p_k$, and $ p_l$ and contains no other points of $ \mathcal{P}$.

These formulations can be expressed in a mathematical way:

$ < p_i p_j p_k p_l >_{\mathrm{Delaunay}}:\quad\forall \; m \neq i,j,k,l$

\begin{gather*}\begin{split}\exists \;p_m \in \Omega^n &\quad\wedge\ Vert\vert ... ...t\vert s-p_i \vert\vert < \vert\vert s-p_m \vert\vert & \end{split}\end{gather*}    

Here, $ s$ is the center of the $ n$-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.

2.4.2 Two-Dimensional Criterion

Figure 2.3: A two-dimensional Voronoi box of the point $ p_i$
\includegraphics[width=7.1cm]{picsconveps/voro.eps}
A two-dimensional Voronoi box is shown in Figure 2.3. In two dimensions the coupling area $ A_{ij}$ degenerates to the length of the Voronoi edge, which bisects the edge $ < p_ip_j >$ and connects the two center-points of the outer-circles of the triangles $ < p_ip_jp_k >$ and $ < p_ip_jp_l >$.

By splitting this area $ A_{ij}$ into the parts $ A_{ij,k}$ and $ A_{ij,l}$ arising from the involved triangles $ < p_ip_jp_k >$ and $ < p_ip_jp_l >$, respectively, the situation depicted in Figure 2.4(a) is obtained. In this context, for each triangle $ < p_ip_jp_k >$ the possibilities shown in Figure 2.4(c) and Figure 2.4(d) exist. The portion $ A_{ij,k}$ can lie inside or outside the half plane which is spanned by the straight line, built by $ p_i$ and $ p_j$, and the point $ p_k$. By definition an inside-portion $ A_{ij,k}$ is signed positive (Figure 2.4(c)) and signed negative if it lies outside (Figure 2.4(d)). In consideration of non-overlapping Voronoi boxes, the sum of both portions has to be positive. And with geometrical considerations (refer Figure 2.4(b))

$\displaystyle \Theta_{k} + \Theta_{l} \leq 180^\circ,$ (2.17)

or equivalently,

$\displaystyle \Theta_{k} \leq 180^\circ - \Theta_{l}$ (2.18)

has to be satisfied.
Figure 2.4: A detail of the Voronoi Region shown before.

\includegraphics[width=7.5cm]{picsconveps/splitvoro.eps}
The components of the Voronoi regions of the triangles $ < p_ip_jp_k >$ and $ < p_ip_jp_l >$.
\includegraphics[width=6.8cm]{picsconveps/exvoro.eps}
The angle criterion for two dimensions. The marginal case with $ A_{ij}=0$ is reached if $ p_k$ lies at the outer-circle of $ < p_ip_jp_l >$.


\includegraphics[width=7.5cm]{picsconveps/oktri.eps}
The center $ m_{ijk}$ of the outer-circle of the triangle $ < p_ip_jp_k >$ lies in the half plane $ < p_ip_j >,p_k$. The portion of the coupling area is positive $ A_{ij,k}>0$.
\includegraphics[width=6.8cm]{picsconveps/badtri.eps}
The center $ m_{ijk}$ of the outer-circle of the triangle $ < p_ip_jp_k >$ lies outside of the half plane $ < p_ip_j >,p_k$. The portion of the coupling area is negative $ A_{ij,k}<0$.
Figure 2.5: Valid and invalid tessellations of two triangles.
$\textstyle \parbox{0.45\linewidth}{ \includegraphics[scale=0.45]{picsconveps/v1}}$
Valid tessellation of two triangles, $ A_{ij,k}>0$ and $ A_{ij,l}>0$
        
$\textstyle \parbox{0.45\linewidth}{ \includegraphics[scale=0.45]{picsconveps/v15}}$
Valid tessellation of the two triangles, $ A_{ij,k}<0$, $ A_{ij,l}>0$ and in sum $ A_{ij}>0$, a non-overlapping Voronoi box remains
$\textstyle \parbox{0.45\linewidth}{ \includegraphics[scale=0.45]{picsconveps/v25}}$
Invalid tessellation of the two triangles, $ A_{ij,k}<0$, $ A_{ij,l}>0$, but $ A_{ij}=A_{ij,k}+A_{ij,l}<0$, an overlapping Voronoi box remains
        
$\textstyle \parbox{0.45\linewidth}{ \includegraphics[scale=0.45]{picsconveps/v3}}$
Invalid tessellation of the two triangles, $ A_{ij,k}<0$ and $ A_{ij,l}<0$, also an overlapping Voronoi box is built

Consequently it follows that if the point $ p_k$ lies inside the outer-circle of the triangle $ < p_ip_jp_l >$, relation (2.18) is violated. If $ p_k$ lies outside or directly on the circle (marginal case), the relation is satisfied. This criterion must be fulfilled for each neighboring triangle-pair of the mesh. Examples for valid and invalid (overlapping) two-dimensional Voronoi edges are shown in Figure 2.5.

With other words:

There must not be any grid point, which lies inside the outer-circle of each triangle.
This is known as the Delaunay criterion for two dimensions.

2.4.2.1 Addendum for Boundary Points

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 $ A_{ij}$ between two boundary points $ p_i$ and $ p_j$ must not be negative (see Figure 2.6). This means, all centers of the outer-circles 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 outer-circle lies at the surface.
\includegraphics[width=7.0cm]{picsconveps/vorob1}
Valid triangulation at the boundary, $ A_{ij}>0$
    
\includegraphics[width=7.5cm]{picsconveps/vorob2}
Invalid triangulation of the boundary, $ A_{ij}<0$


2.4.3 Three-Dimensional Criterion

Figure 2.7: The coupling areas of a three-dimensional tetrahedral Delaunay grid around the point $ p_i$.
\includegraphics[width=6.9cm]{htmlpicsconveps/newbox}
Typical Voronoi box around a grid point $ p_i$
        
\includegraphics[width=6.9cm]{htmlpicsconveps/box2}
Detail of the box, the coupling area between the point $ p_i$ and $ p_j$



\includegraphics[width=6.9cm]{htmlpicsconveps/box3}
Viewing the coupling area along the edge $ < p_ip_j >$
        


\includegraphics[width=6.9cm]{htmlpicsconveps/box5}
Separated situation

For the three-dimensional case such an area $ A_{ij}$ 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 outer-circle of the appropriate triangle and the center of the outer-sphere 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.

$\textstyle \parbox{6.7cm}{\center \includegraphics[height=7.5cm]%width=6.5cm] {picsconveps/detail11} }$
Valid coupling area, the portions of both tetrahedrons are positive
        
$\textstyle \parbox{6.7cm}{\center \includegraphics[height=7.5cm]%width=6.5cm] {picsconveps/detail22} }$
Valid coupling area, one positive and one negative portion, in sum a positive, non-overlapping area remains

$\textstyle \parbox{6.7cm}{\center \includegraphics[height=7.5cm]%width=6.5cm] {picsconveps/detail44} }$
Invalid coupling, one positive and one negative coupling portion, an overlapping area is constructed
        
$\textstyle \parbox{6.7cm}{\center \includegraphics[height=8cm]%width=6.5cm] {picsconveps/detail55} }$
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 outer-sphere of each tetrahedron.

But different to the two-dimensional case, no simplified angle criterion can be declared for three dimensions.

2.4.3.1 Addendum for Boundary Points

Also for three-dimensional Delaunay grids, the coupling area $ A_{ij}$ between two boundary points $ p_i$ and $ p_j$ must not be negative. The three-dimensional 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 outer-sphere lies at the surface.
\includegraphics[width=7.2cm]{picsconveps/oktet3}
Valid surface triangulation, coupling areas at the surface are positive, the center of the outer-sphere of the tetrahedron lies inside
    
\includegraphics[width=7.2cm]{picsconveps/badtet3}
Invalid surface triangulation, negative coupling areas, the center of the outer-sphere of the tetrahedron lies outside
next up previous contents
Next: 2.5 Demands for Finite Up: 2. Grid Types Previous: 2.3 Grid Requirements
J. Cervenka: Three-Dimensional Mesh Generation for Device and Process Simulation