Subsections

• 2.1.1 $n$ -Simplex
• 2.1.2 Standard $n$ -Simplex
• 2.1.3 $m$ -Face
• 2.1.4 Convex Hull
• 2.1.5 Covering Up
• 2.1.6 Triangulation
• 2.1.7 Mesh
• 2.1.8 Conformal Mesh
• 2.1.9 Mesh Element

2.1 General Definitions

In the following, different algorithms for tetrahedral mesh adaptation are developed to fulfill state-of-the-art demands of TCAD simulations. First some definitions of commonly used technical terms have to be given, to provide the non-experienced reader with some convenient descriptions. Slightly different definitions can be found in literature, but the following ones are in the style of explanations given in [4].

2.1.1 $n$ -Simplex

Definition 1 ($n$ -simplex)   In geometry, a simplex or $n$ -simplex is an $n$ -dimensional analogon of a triangle. Specifically, a simplex is the convex hull of a set of $(n + 1)$ affinely independent points in some Euclidean space of dimension n or higher (i.e., a set of points such that no m-plane contains more than $(m + 1)$ of them; such points are said to be in general position). A regular simplex is a simplex that is also a regular polytope.

For example, a 0-simplex is a point, a 1-simplex is a line segment, a 2-simplex is a triangle, a 3-simplex is a tetrahedron, and a 4-simplex is a pentachoron, also known as pentatope (in each case with interior) in its adequate dimension.

A tetrahedron is a polyhedron composed of four triangular faces, three of which meet at each vertex. A regular tetrahedron is one in which the four triangles are regular, or "equilateral", and is one of the Platonic solids. A tetrahedron is referred as a 3-simplex.

2.1.2 Standard $n$ -Simplex

Definition 2 (standard $n$ -simplex)   The standard $n$ -simplex is the subset of $\mathbb{R}^{n+1}$ given by

$$\bigtriangleup{}^n = \{ (t_0,\ldots{},t_n) \in \mathbb{R}^{n+1} \; \vert \; \sum_{i} t_i = 1 \; \wedge \; t_i \geq 0 \; \forall i \}.$$ (2.1)

Removing the restriction $t_{i} \geq 0$ in (2.1) gives an $n$ -dimensional affine subspace of $\mathbb{R}^{n+1}$ containing the standard $n$ -simplex. The vertices of the standard $n$ -simplex are the points

$$e_0 = (1,0,0,\ldots ,0),\notag$$ (2.2)

$$e_1 = (0,1,0,\ldots ,0),\notag$$ (2.3)

$$\vdots \notag$$ (2.4)

$$e_n = (0,0,0,\ldots ,1). \notag$$ (2.5)

2.1.3 $m$ -Face

Definition 3 ($m$ -face)   The convex hull of any $m$ points of an $n$ -simplex is also a simplex, called an $m$ -face. The 0 -faces are called the vertices, the $1$ -faces are called the edges, the $(n - 1)$ -faces are called the facets, and the sole $n$ -face is the whole $n$ -simplex itself.

2.1.4 Convex Hull

Definition 4 (Convex hull)   The convex hull of a set of points $S$ in $n$ dimensions is the intersection of all convex sets containing $S$ . For $N$ points $p_1 , \ldots , p_N$ , the convex hull $C$ is then given by the expression

$$C \equiv \bigg \{ \sum_{j=1}^{N} \lambda_j p_j : \lambda_j \geq 0 \;\;\; \forall j \; \wedge \sum_{j=1}^{N} \lambda_j = 1 \bigg \}.$$

In $d$ dimensions, the gift wrapping algorithm [33], which has complexity $\mathcal{O}(n^{\lfloor d/2 \rfloor + 1})$ , where $\lfloor x \rfloor$ is the floor function, can be used. In two and three dimensions, however, specialized algorithms exist with complexity $\mathcal{O}(n \log_2 n)$ .

2.1.5 Covering Up

Let $S$ be a (finite) set of points in $\Bbb{R}^d$ ( $d \in \{2,3\}$ ), the convex hull of $S$ , denoted as $\operatorname{conv}(S)$ , defines a domain $\Omega$ in $\Bbb{R}^d$ . Let $K$ be a simplex, then the covering up $\mathcal{T}_r$ of $\Omega$ by means of such elements corresponds to the following:

Definition 5 (Covering up)   $\mathcal{T}_r$ is a simplicial covering up of $\Omega$ if the following conditions hold

• $(C_1)$ The set of element vertices in $\mathcal{T}_r$ is exactly $S$ .
• $(C_2)$ $\Omega = \overset{\circ}{ \overline{\underset{K \in \mathcal{T}_r }\bigcup K}}$ , where $K$ is a simplex.
• $(C_3)$ The interior of every element $K$ in $\mathcal{T}_r$ is non empty.
• $(C_4)$ The intersection of the interior of two elements is an empty set.

Here is a natural definition: with respect to condition $(C_1)$ , one can see that $\Omega$ is the open set corresponding to the domain that means, in particular, that $\overline{\Omega} = \underset{K \in \mathcal{T}_r }{\bigcup} K$ . Condition $(C_2)$ is not strictly necessary to define a covering up, but it is nevertheless practical with respect to the context and, thus, will be assumed. Condition $(C_3)$ means that element overlapping is proscribed [4].

2.1.6 Triangulation

Definition 6 (Triangulation)   $\mathcal{T}_r$ is a conforming triangulation or simply a triangulation of $\Omega$ , if $\mathcal{T}_r$ is a covering up following Definition 5 and if, in addition, the following condition holds:

• $(C_5)$ the intersection of two elements in $\mathcal{T}_r$ is either reduced to
  • the empty set or
  • a vertex, an edge, or a face (for $d=3$ ).

More generally, in $d$ dimensions, such an intersection must be a $k$ -face, for $k= -1, \ldots , d-1$ , where $d$ is the spatial dimension, and the $-1$ -face is the empty set.

2.1.7 Mesh

Let $\Omega$ be a closed bounded domain in $\Bbb{R}^d$ ( $d \in \{2,3\}$ ). The question is how to construct a confirming triangulation of this domain. Such a triangulation will be referred to as a mesh of $\Omega$ and will be denoted by $\mathcal{T}_h$ .

Definition 7 (Mesh)   $\mathcal{T}_h$ is a mesh of $\Omega$ if

• $(C_1)$ $\Omega = \overset{\circ}{ \overline{\underset{K \in \mathcal{T}_h }\bigcup K}}$ .
• $(C_2)$ The interior of every element $K$ in $\mathcal{T}_h$ is non empty.
• $(C_3)$ The intersection of the interior of two elements is empty.

In contrast, Definition 5-$(C_1)$ is no longer assumed, which means that the vertices are not in general, given a priori and in Definition 7-$(C_1)$ , the $K$ s are not necessarily simplices.

2.1.8 Conformal Mesh

Most computational schemes using a mesh as a spatial support assume that this mesh is conformal (although, this property is not strictly necessary for some solution methods).

Definition 8 (Conformal Mesh)   $\mathcal{T}_h$ is a conformal mesh of $\Omega$ if

• Definition 7 holds and
• $(C_4)$ the intersection of the interior of two elements in $\mathcal{T}_h$ is either,
  • the empty set, a vertex, an edge or a face (when $d=3$ ).

2.1.9 Mesh Element

Elements are the basic components of a mesh. An element is defined by its geometric nature and a list of vertices.

Definition 9 (Connectivity)   The connectivity of a mesh element is the definition of the connections between the vertices at the element level.

Definition 10 (Topology)   The topology of a mesh element is the definition of this element in terms of its facets and edges, these last two being defined in terms of the element's vertices.

Remark 1 (Mesh)   In the following a conformal mesh with tetrahedral mesh elements ($3$ -simplex) are referred simply as mesh. Other meanings or specifications are pointed out explicitely.