2.3.1 Delaunay Properties

Delaunay's criterion [83] defines a property essential for grids used in device simulation. It is based on the definition of Voronoi boxes [95,96]. It is to note, that Delaunay's criterion and the definition of Voronoi boxes are dual, which can be seen in Fig. 2.8. The following fundamental definitions are based on definitions found in [83,88].

Definition 2..1 (Voronoi)   Let $\mathcal{P}=\{P_1, P_2, \ldots, P_n\}$ be a finite set of points in $m$-dimensional space with their location vectors $\mathbf{x}_i \ne \mathbf{x}_j \;\: \forall \;\: i \ne j$. All points belong to a grid which represents the $m$-dimensional region ${\Omega}$. Each point ${P}_{i}$ is assigned a box ${{\Omega}}_{i}$ defined by

$${{\Omega}}_{i}= \{ \mathbf{x} \;\; \vert \;\;\, \vert\mathbf{x} -... ...{x} - \mathbf{x}_j\vert \;\: \forall \;\: i \ne j, \: \mathbf{x} \in {\Omega}\}$$

called Voronoi box with its volume ${V}_{i}$. The union $\mathcal{V}$ of all Voronoi boxes is called Voronoi-diagram.

Fig. 2.8(a) shows the Voronoi box ${{\Omega}}_{i}$ with its Volume ${V}_{i}$ for a point ${P}_{i}$ of a two-dimensional grid. As the two-dimensional simulations assume a constant device width in the third dimension, the actual box volume is determined by multiplication by the width. Fig. 2.8(a) can be found in many publications [45,73,74,88]. Fig. 2.8(b) shows the Voronoi box ${{\Omega}}_{i}$ with its volume ${V}_{i}$ for a point ${P}_{i}$ of a three-dimensional grid. Both pictures clearly show, that the Voronoi box ${{\Omega}}_{i}$ is the set of all locations $\mathbf{x}$ which are nearer to ${P}_{i}$ than to any other point of the grid.

Figure 2.8: Voronoi boxes of Delaunay grids.

(a) Two-dimensional Voronoi box.

(b) Three-dimensional Voronoi box.

In Fig. 2.8(a) the grid lines are drawn thick. The thin lines show the Voronoi boxes. For reasons of clearness of the picture, the line thickness has been chosen inversely in Fig. 2.8(b). The grid and the Voronoi-diagram are dual.

Definition 2..2 (Delaunay element)   Let $\mathcal{P}=\{P_1, P_2, \ldots, P_n\}$ be a finite set of points in the $m$-dimensional space with their location vectors $\mathbf{x}_i \ne \mathbf{x}_j \;\: \forall \;\: i \ne j$. All points belong to a grid which represents the $m$-dimensional region ${\Omega}$. Let $\mathbf{x}$ be an arbitrary location in ${\Omega}$. The $k+1$ linear independent points $\mathcal{P}_{\text{D},k}$ with $1 \le k \le m$ form a $k$-dimensional Delaunay element $T_{\text{D},k}$ if and only if there exists a location $\mathbf{x}$ which is equally close to all points $\mathcal{P}_{\text{D},k}$ and closer to all points $\mathcal{P}_{\text{D},k}$ than to any other point ${P}_{i}\not\in \mathcal{P}_{\text{D},k}$. The location $\mathbf{x}$ then is the center of a $k$-dimensional sphere which passes through all points of $\mathcal{P}_{\text{D},k}$ which is the $k$-dimensional circumsphere of the Delaunay element $T_{\text{D},k}$.

$$T_{\text{D},k} (\mathcal{P}_{\text{D},k}) \Longleftrightarrow \exists \, \mathbf{x}$$

$$\mathbf{x} \in {\Omega}\quad \wedge$$

$$\vert\mathbf{x} - \mathbf{x}_i\vert = \vert\mathbf{x} - \mathbf{x}_j\vert \;\: \forall \;\: {P}_{i}, P_j \in \mathcal{P}_{\text{D},k} \quad \wedge$$

$$\vert\mathbf{x} - \mathbf{x}_i\vert < \vert\mathbf{x} - \mathbf{x... ... \;\: {P}_{i}\in \mathcal{P}_{\text{D},k}, P_j \not\in \mathcal{P}_{\text{D},k}$$

A Delaunay triangle consists of Delaunay edges, a Delaunay tetrahedron consists of Delaunay triangles and Delaunay edges. Fig. 2.9(a) shows a single Delaunay triangle and its two-dimensional Voronoi boxes. The center of the circumcircle is found by the intersection of the bisecting lines of the edges. Fig. 2.9(b) shows a single Delaunay tetrahedron and its Voronoi boxes. The center of the circumsphere is the intersection of all bisecting planes of the edges.

(a)  Voronoi diagram of a triangle.

(b)  Voronoi diagram of a tetrahedron.

Figure 2.9: Voronoi boxes of primitive two- and three-dimensional grid elements.

Voronoi boxes of points at a surface propagate in the other region. For the discretization (see Section 2.4) it is necessary to truncate the box at the surface. Therefore, the surface of ${\Omega}$ is the border of the box ${{\Omega}}_{i}$ of the point ${P}_{i}$ on the surface (see Fig. 2.10).

Figure 2.10: Voronoi box of a point at the surface.

Fig. 2.11 shows two possible triangulations for four given points $P_1$, $P_2$, $P_3$, and $P_4$. The triangulation shown in Fig. 2.11(a) is a valid Delaunay triangulation. The dual Voronoi boxes are disjunct and can be clearly assigned to their corresponding grid points.

(a)  Delaunay triangulation.

(b)  Non-Delaunay triangulation.

Figure 2.11: Correct and incorrect Voronoi boxes caused by different triangulation.

The triangulation shown in Fig. 2.11(b) is a non-Delaunay triangulation since each circumcircle contains a point of the other triangle. The boxes are derived from the duality principle and are no Voronoi boxes. The volumes of the dual boxes are listed in Table 2.1. Because Delaunay's criterion is violated the volumes calculated are wrong which introduces an error in the discretization. In other words Voronoi boxes are desired. To calculate them the duality principle is required. For that reason Delaunay's criterion Definition 2.2 is mandatory for grids used in device simulation.

Table 2.1: Volumes of the boxes shown in Fig. 2.11(b).

${P}_{i}$	${V}_{i}$
$P_1$	$V_1 + V_5 + V_6$
$P_2$	$V_2 - V_5$
$P_3$	$V_3 + V_5 + V_6$
$P_4$	$V_4 - V_6$

Fig. 2.12(a) shows a slightly different example of a two-dimensional grid. The circumcircles shown in Fig. 2.12(b) only contain the points of the corresponding triangles. Thus, the triangulation fulfills Delaunay's criterion and the resulting boxes (Fig. 2.12(c)) are valid Voronoi boxes.

(a)  Triangulation with obtuse angles.

(b)  Both triangles fulfill the Delaunay criterion.

(c)  Resulting Voronoi boxes.

Figure 2.12: Adverse Voronoi boxes due to obtuse angles.

Nevertheless, the triangulation which is caused by the obtuse angled triangle is adverse since fluxes between the points $P_1$ an $P_3$ are discretized using the area $A_{13}$ which is far from the grid line $P_1 - P_2$. Moreover, elements like needles with no obtuse but a small angle result in a circumsphere with a large radius and cause numerical problems [83].

As a conclusion grids suitable for three-dimensional device simulation must consist of elements which satisfy Delaunay's criterion ( Definition 2.2). Moreover obtuse and small angled elements should be avoided.