A Mathematical and Geometrical Background

Mathematical and geometrical definitions and lemmas as well as proof of lemmas important for this work are presented in this appendix. Unless explicitly stated otherwise, the topological vector space $({\mathbb{R}}^n, \tau_n), n \geq 1$, where $\tau_n$ is the standard topology induced by the Euclidean norm^9.1, is used throughout this thesis. More specifically, this work focuses on the topological vector spaces $({\mathbb{R}}^2, \tau_2)$ and $({\mathbb{R}}^3, \tau_3)$.

$g \circ f$ therefore maps from the domain $\operatorname{dom}(g \circ f) = f^{-1} \left( \operatorname{img}(f) \cap \operatorname{dom}(g) \right)$ to the image $\operatorname{img}(g \circ f) = g\left( \operatorname{img}(f) \cap \operatorname{dom}(g) \right)$. The composition of two functions $g$ and $f$ is invalid, if $\operatorname{img}(f) \cap \operatorname{dom}(g) = \emptyset$.

Every connected set is trivially piecewise connected. A closed bounded set in ${\mathbb{R}}^n$ is compact. Figure A.1 visualizes the connected property.

Figure A.1: Connected property of sets

For bottom set, choosing the blue subset to represent $X_1$ and the red subset to represent $X_2$ yields a partition of the set with $\operatorname{cl}(X_1) \cap X_2 = X_1 \cap \operatorname{cl}(X_2) = \emptyset$. Therefore, the bottom set is not connected. For the top set, no such two sets exist.

A hyperplane is defined a linear subset of ${\mathbb{R}}^n$ which has a dimension of $n-1$:

An important type of subsets of ${\mathbb{R}}^n$ are manifolds.

In the literature, manifolds are usually not required to be compact and do not include their boundary. The definition in this work has been chosen to ease notation.

The standard definition of the interior and the boundary is non-intuitive for $k$-manifolds in ${\mathbb{R}}^n$ with $k < n$. For example, the interior of a triangle $T$ in ${\mathbb{R}}^3$ is empty and the boundary (defined as the closure without the interior) is $\operatorname{cl}(T)$. Therefore, a more intuitive definition of the interior and the boundary of manifolds is used in this work:

The boundary of a $k$-manifold is a $k-1$-manifold. For example, the closed unit $n$-ball $\overline{\mathcal{B}}^n$ is an $n$-manifold. The interior of $\overline{\mathcal{B}}^n$, $\operatorname{int}^\star (\overline{\mathcal{B}}^n)$, is the open unit $n$-ball ${\mathcal{B}}^n$. The boundary of $\overline{\mathcal{B}}^n$ ${\operatorname{bnd}}^\star (\overline{\mathcal{B}}^n)$ is the set $\{ \bm{x} \in {\mathbb{R}}^n, {\left\lVert\bm{x}\right\rVert_2} = 1 \}$ which is an $n-1$-manifold. Some properties of manifolds are presented in the next lemma.

Lemma 1 (Manifold properties)   Let $X,A,B \subseteq {\mathbb{R}}^n$ be manifolds.

(i)

$X$ is a $k$-manifold if and only if $\operatorname{int}^\star _k(X) \neq \emptyset$.

(ii)

Let $A \subseteq B$. Then, ${\operatorname{DIM}}(A) \leq {\operatorname{DIM}}(B)$.

(iii)

Let $A \subseteq B$. Then, for $k \geq {\operatorname{DIM}}(B)$, $\operatorname{int}^\star _k(A) \subseteq \operatorname{int}^\star _k(B)$.

(iv)

Let $A$ and $B$ be manifolds. Then, for $k \geq \max({\operatorname{DIM}}(A),{\operatorname{DIM}}(B))$, $\operatorname{int}^\star _k(A \cap B) = \operatorname{int}^\star _k(A) \cap \operatorname{int}^\star _k(B)$.

Proof. $$

(i)

Follows trivially from the definition of a manifold and the relative interior.

(ii)

Assume, ${\operatorname{DIM}}(A) > {\operatorname{DIM}}(B)$, then there is an $\bm{x} \in A$ which is also in $B$. $\bm{x}$ has a neighbor $U_B$ based on the topology $\tau_n \vert_B$ which is homeomorph to ${\mathcal{B}}^{{\operatorname{DIM}}(B)}$. $\bm{x}$ has also a neighborhood $U_A$ based on the topology $\tau_n \vert_A$ which is homeomorph to ${\mathcal{B}}^{{\operatorname{DIM}}(A)}$. Because $A \subseteq B$, $U_A$ is a subset of $B$. $U_A$ can be scaled down to be a subset of $U_B$. However, there is no neighborhood $U_A$ which is homeomorph to ${\mathcal{B}}^{{\operatorname{DIM}}(A)}$ which is a subset of $U_B$ (which is homeomorph to ${\mathbb{R}}^{{\operatorname{DIM}}(B)}$) with ${\operatorname{DIM}}(A) > {\operatorname{DIM}}(B)$. Therefore, ${\operatorname{DIM}}(A)$ has to be less or equal to ${\operatorname{DIM}}(B)$.

(iii)

For $k > {\operatorname{DIM}}(B)$, $\operatorname{int}^\star _k(A)$ and $\operatorname{int}^\star _k(B)$ is empty. Otherwise, for ${\operatorname{DIM}}(A) < k$ ( ${\operatorname{DIM}}(A)$ can not be larger than $k$ due to (ii)), $\operatorname{int}^\star _k(A)$ is empty.

Let ${\operatorname{DIM}}(A) = {\operatorname{DIM}}(B) = k$. For every $\bm{x} \in \operatorname{int}^\star _k(A)$ there is a neighborhood $U_A$ of $\bm{x}$ based on the topology $\tau_n \vert_A$ which is homeomorph to ${\mathcal{B}}^k$. Because $A \subseteq B$, $\bm{x}$ is also in $B$. Every neighborhood of $\bm{x}$ based on the topology $\tau_n \vert_B$ is either homeomorph to ${\mathcal{B}}^k$ or ${\mathcal{H}}^k$. Because $U_A$ is also a subset of $B$, every neighborhood of $\bm{x}$ based on the topology $\tau_n \vert_B$ has to be homeomorph to ${\mathcal{B}}^k$. Therefore, $\bm{x}$ is in $\operatorname{int}^\star _k(B)$.

(iv)

If ${\operatorname{DIM}}(A) < k$ or ${\operatorname{DIM}}(B) < k$, $\operatorname{int}^\star _k(A \cap B)$ and $\operatorname{int}^\star _k(A) \cap \operatorname{int}^\star _k(B)$ are empty.

Let ${\operatorname{DIM}}(A) = {\operatorname{DIM}}(B) = k$. For $\bm{x} \in \operatorname{int}^\star _k(A) \cap \operatorname{int}^\star _k(B)$, $\bm{x}$ is in $\operatorname{int}^\star _k(A)$ and has a neighborhood $U_A$ based on the topology $\tau_n \vert_A$ which is homeomorph to ${\mathcal{B}}^k$. Also, $\bm{x}$ is in $\operatorname{int}^\star _k(B)$ and has a neighborhood $U_B$ based on the topology $\tau_n \vert_B$ which is homeomorph to ${\mathcal{B}}^k$. $U_A \cap U_B$ is a neighborhood based on the topology $\tau_n \vert_{A \cap B}$ of $\bm{x}$ which is homeomorph to ${\mathcal{B}}^k$. Therefore, $\operatorname{int}^\star _k(A) \cap \operatorname{int}^\star _k(B)$ is a subset $\operatorname{int}^\star _k(A \cap B)$.

On the other hand, every $\bm{x} \in \operatorname{int}^\star _k(A \cap B)$ has a neighborhood $U_{A \cap B}$ based on the topology $\tau_n \vert_{A \cap B}$ which is homeomorph to ${\mathcal{B}}^k$. Every neighborhood $U_A$ of $\bm{x}$ based on the topology $\tau_n \vert_A$ is either homeomorph to ${\mathcal{B}}^k$ or ${\mathcal{H}}^k$. The neighborhood $U_{A \cap B}$ can be scaled down to be a subset of $U_A$. Therefore, $U_A$ has to be homeomorph to ${\mathcal{B}}^k$ leading to $\bm{x}$ also being in $\operatorname{int}^\star _k(A)$. A similar argument can be applied to the set $B$. Therefore, $\bm{x}$ is in $\operatorname{int}^\star _k(A)$ and in $\operatorname{int}^\star _k(B)$ and consequently $\operatorname{int}^\star _k(A \cap B)$ is a subset of $\operatorname{int}^\star _k(A) \cap \operatorname{int}^\star _k(B)$.

$\qedsymbol$

The boundary of manifolds used in this work can be represented as union of other manifolds with lower dimensions. For example, the boundary of a triangle can be represented as the union of its three lines. Boundary elements which are maximal, i.e. there are no larger elements which are included in the boundary, are called facets. The facets and recursively all facets of facets of a manifold are called faces.

The ${\operatorname{DIM}}(E)$-dimensional faces of an element $E$ is $E$ itself ( ${\operatorname{faces}}_{{\operatorname{DIM}}(E)}(E) = \left\{E\right\}$) and the ${\operatorname{DIM}}(E)-1$-dimensional faces are the facets ( ${\operatorname{faces}}_{{\operatorname{DIM}}(E)-1}(E) = {\operatorname{facets}}(E)$).

Figure A.2: Element faces are not minimal

The element space ${\mathcal{E}}$ represents a triangle with two polylines boundary elements and three vertices. The boundary of the triangle can be represented as the union of the two polylines. However, the line connecting the lower two vertices occurs twice in that union.

Intuitively, the facets of an element $E$ should be a minimal cover of its boundary ${\operatorname{bnd}}^\star (E)$. Figure A.2 visualizes an element space where the boundary representation of a cell is not minimal. Therefore, the term face-complete is introduced:

Similar to the faces and facets, the co-faces and co-facets of an element $E$ are defined as the elements of which $E$ is a face or a facet, respectively.

Elements which share a common face are called neighbors.

A very important property, especially for discretization-based simulation methods, is conformity. The intersection of two different elements of a conforming element space is a face of both elements. This property enables straight-forward interfaces between two neighboring cells which simplifies interaction between them.

Conforming element spaces play a central role in this work.

Connected compact $k$-manifolds are the basic building blocks of meshes, called mesh elements. Linear mesh elements are the most basic elements used in this work. They are defined using affine and convex hulls.

Figure A.3: Affine and convex hull

The left row visualizes different sets of points. The affine hull and the convex hull of the corresponding point set is given in the middle row and the right row, respectively.

An affine combination with all weights $w_i \geq 0$ is called a convex combination. The convex hull of a set is equal to all convex combinations of points from that set. Figure A.3 shows examples of the affine and convex hull of different sets of points.

The most basic linear mesh elements are called simplices.

Figure A.4: Simplices

From left to right: a 0-simplex (vertex), a $1$-simplex (line, edge), a $2$-simplex (triangle), and a $3$-simplex (tetrahedron).

A 0-simplex is called a vertex, a $1$-simplex is called a line or edge, a $2$-simplex is called a triangle, and a $3$-simplex is called a tetrahedron. Simplices are visualized in Figure A.4. $_{\widetilde{\operatorname{simplices}}}{\mathcal{E}}_k^n$ is empty for $k>n$ because there are there are no affinely independent sets of $k$ points in ${\mathbb{R}}^n$.

Figure A.5: Faces

From left to right: a tetrahedron, its 2D faces (four triangles), its 1D faces (six edges), and its 0D faces (four vertices).

For every vertex $V \in _{\operatorname{simplices}}{\mathcal{E}}^n$, its facet set and therefore its face set is empty. For every other $k$-simplex $S$ being the convex hull of $\{\bm{s}_1, \dots, \bm{s}_{k+1}\}$, all facets of $S$ are simplices using a $k-1$-subset:

$${\operatorname{facets}}_{_{\operatorname{simplices}}{\mathcal{E}}... ..._1, \dots, \bm{s}_{i-1}, \bm{s}_{i+1}, \dots, \bm{s}_{k+1}, 1 \leq i \leq k) \}$$ (9.1)

Figure A.5 visualizes a tetrahedron with all of its faces.

Non-trivial linear elements are called polyhedrons:

Convex $k$-polyhedra and linear $k$-cells are compact $k$-manifolds. A linear 0-cell is a vertex, a linear $1$-cell is a line, a linear $2$-cell is a called a polygon, and a linear $3$-cell is called a (not necessarily convex) polyhedron.

Although this work mainly focuses on simplices, some algorithms and proofs also hold for a larger class of elements. A hypercube-motivated approach is used to define more elements, especially quadrilaterals and hexahedrons.

To exclude exotic subsets of ${\mathbb{R}}^n$, only parameterizations which lead to manifolds are allowed (restriction (i)). Restriction (ii) prevents the parameterized element from being degenerated and self-intersecting. The third restriction (iii) ensures, that the parameterized element is bounded and closed and therefore compact. Additionally, (iii) gives a parameterization for the boundary of the parameterized element.

The definition of the $k$-interpolation combination is motivated by the recursive parameterization of a hypercube. Note, that a $k$-interpolation combination is not a linear function in general. Therefore, when using a parameterized element based on a $k$-interpolation combination, the element does not need to be linear. However, for fixed $\alpha_1, \dots, \alpha_{i-1}, \alpha_{i+1}, \dots, \alpha_{2^k}$ the $k$-interpolation combination is linear in $\alpha_i$.

When using pairwise different points, the parameterized element using a $2$-interpolation combination results in a quadrilateral and using a $3$-interpolation combination results in a hexahedron. The $k$-interpolation combination is injective for these element types.

Quadrilaterals in ${\mathbb{R}}^2$ are convex and their boundary is piecewise linear. The facets of a quadrilateral are four lines:

$${\operatorname{facets}}_{_{\operatorname{quad}}{\mathcal{E}}^n}({... ...{q}_4\}), {\operatorname{simplex}}(\{\bm{q}_3, \bm{q}_4\}) \end{array} \right\}$$ (9.2)

The facets of a hexahedron are six quadrilaterals:

$${\operatorname{facets}}_{_{\operatorname{hex}}{\mathcal{E}}^n}({\... ...ratorname{quad}}((\bm{h}_3, \bm{h}_4, \bm{h}_7, \bm{h}_8)) \end{array} \right\}$$ (9.3)

While mixed element spaces with triangle and quadrilateral cell elements can be conforming, more element types are required for 3D element spaces because tetrahedrons and hexahedrons do not share any facet type. Mixed element spaces are not a focus of this work, however for the sake of completeness two additional element types are defined using a non-injective $k$-interpolation combination. A $3$-interpolation combination where the last four points are all the same results in a pyramid. A $3$-interpolation combination, where the 3rd and 4th as well as the 7th and the 8th point are equal results in a triangular prism, also called wedge.

The facets of a pyramid are four triangles and one quadrilateral:

$${\operatorname{facets}}_{_{\operatorname{pyramid}}{\mathcal{E}}^n... ...ratorname{quad}}((\bm{p}_1, \bm{p}_2, \bm{p}_3, \bm{p}_4)) \end{array} \right\}$$ (9.4)

The facets of a wedge are two triangles and three quadrilaterals:

$${\operatorname{facets}}_{_{\operatorname{wedge}}{\mathcal{E}}^n}(... ...ratorname{quad}}((\bm{w}_2, \bm{w}_1, \bm{w}_5, \bm{w}_4)) \end{array} \right\}$$ (9.5)

Examples of quadrilaterals, hexahedrons, pyramids, and wedges are shown in Figure A.6.

Figure A.6: Non-simplex elements

From left to right: a quadrilateral, a hexahedron, a pyramid, and a wedge.

Simplices can also be represented using parameterized elements: ${\mathcal{P}}(I_{(\bm{l}_1, \bm{l}_2)})$ is a line,
${\mathcal{P}}(I_{(\bm{t}_1, \bm{t}_2, \bm{t}_3, \bm{t}_3)})$ is a triangle, and ${\mathcal{P}}(I_{(\bm{e}_1, \bm{e}_2, \bm{e}_3, \bm{e}_3, \bm{e}_4, \bm{e}_4, \bm{e}_4, \bm{e}_4)})$ is a tetrahedron. All elements presented here are connected compact manifolds. A vertex is a 0-manifold, a line is a $1$-manifold, triangles and quadrilaterals are $2$-manifolds, and tetrahedrons, hexahedrons, pyramids, and wedges are $3$-manifolds.

The presented mesh elements are combined in the mesh element space which is defined as follows:

The geometry space $\mathfrak{L}^n$ is equal to the set of all polyhedra which are manifolds: $\mathfrak{L}^n = \mathfrak{M}^n \cap _{\operatorname{poly}}{\mathcal{E}}^n$. The element spaces $_{\operatorname{simplices}}{\mathcal{E}}_k^n$, $_{\operatorname{quad}}{\mathcal{E}}^n$, $_{\operatorname{hex}}{\mathcal{E}}^n$, $_{\operatorname{pyramid}}{\mathcal{E}}^n$, $_{\operatorname{wedge}}{\mathcal{E}}^n$, and ${\mathfrak{E}}^n$ are face-complete for $k \geq 0, n \geq 1$.

However, it is generally not possible to have a non-trivial partition of a closed set consisting of closed sets. Therefore, a slight abstraction of a partition is defined.

A manifold partition of a $k$-manifold allows for an arbitrary number of - not necessarily disjunct - manifolds which have a dimension less than $k$. For example, the closed unit $n$-ball can have a valid manifold partition which consists of the closed unit $n$-ball itself and its boundary. Using this definition, it is possible to create a manifold partition of a $k$-manifold $X$ using manifolds.

Figure A.7: The intersection of manifolds is not a manifold

The intersection of the two manifolds colored in blue and red is highlighted in green. This intersection is not a manifold.

The choice of $\mathfrak{L}^n$ and ${\mathfrak{E}}^n$ only containing linear elements is motivated by the requirements for the boundary patch partition (cf. Section 4.3), which requires the intersection of sets. This intersection should be representable by mesh elements or geometries. However, the intersection of two manifolds is generally not a manifold. This is even true for simple manifolds as visualized in Figure A.7. Instead of representing the intersection of sets with a single mesh element or geometry, the approach used in this work is to represent the intersection as a union of mesh elements or geometries.

In general, the intersection partition is not unique. Due to the definition of conformity, every element complex is IPC.

Lemma 2 ( $\mathfrak{M}^n$ is not IPC)   The set of all manifolds $\mathfrak{M}^n$ is not IPC.

Proof. Let $C,X \subseteq {\mathbb{R}}^{n-1}$ be two non-empty compact sets with $C \subseteq X$ and $f(\bm{x}) = \operatorname{dist}(\bm{x},C)$. Then, $f$ is continuous and $f(\bm{x}) = 0$ if and only if $\bm{x} \in C$. Let $A \subseteq X \times [0, \operatorname{diam}(X)]$ be the graph of $f$ and $B = X \times \{0\}$. $A$ and $B$ are $n$-manifolds and their intersection is $C$.

Choosing $X = [0,1]^{n-1}$ and $C = \{ 1/n \vert n \in {\mathbb{N}}\} \times [0,1]^{n-2}$ yields $A$ and $B$ being $n$-manifolds. However, there is no finite manifold partition of $A \cap B = C$. $\qedsymbol$

The geometry space $\mathfrak{L}^n$, however, is IPC.

Lemma 3 ( $\mathfrak{L}^n$ is IPC)   The geometry space $\mathfrak{L}^n$ is IPC.

Proof. $$ For $A,B \in \mathfrak{L}^n$, $A$ and $B$ can be represented as a finite union of simplices: $A = \bigcup_{i=1}^k A_i$, $B = \bigcup_{j=1}^m B_j$. The intersection $A \cap B$ can be reformulated in the following way:

$$A \cap B = \left( \bigcup_{i=1}^k A_i \right) \cap \left( \bigcup_{j=1}^m B_j \right) = \bigcup_{i=1}^k \bigcup_{j=1}^m A_i \cap B_j$$ (9.6)

The intersection of the simplices $A_i$ and $B_i$ can be represented as a finite union of simplices. Therefore, $A \cap B$ can be represented as a finite union of simplices and $\mathfrak{L}^n$ is IPC. $\qedsymbol$

The partition of two sets used for the IPC property is called the intersection partition.

Every element $C$ of an intersection partition of two sets $X$ and $Y$ is naturally a subset of the intersection of $X \cap Y$. Additionally, according to Lemma A.1, the dimension of every element $C_i$ of the intersection partition of $A$ and $B$ is at most $\min({\operatorname{DIM}}(A),{\operatorname{DIM}}(B))$.

Two manifold partitions of the same set $X$ can be combined to create a finer manifold partition. The intuitive approach for a refinement of two manifold partitions would look like this:

$$S_1 \cap S_2 \overset{?}{:=} \left\{ A \cap B \vert A \in S_1, B \in S_2 \right\}$$ (9.7)

However, as mentioned above, the intersection of two manifolds is not a manifold, but for $A, B \in \mathfrak{L}^n$ the intersection partition can be used. The refinement of two manifold partitions is defined as follows:

Lemma 4 (Refinement of manifold partition is manifold partition)   The refinement of two manifold partitions $S, P$ of a set $X \in \mathfrak{L}^n$ is a manifold partition of $X$.

Proof. $$

(i)

To prove: $\vert\operatorname{refine}(S, P)\vert < \infty$:
The finite combination of finite sets is again finite.

(ii)

To prove: $\emptyset \notin \operatorname{refine}(S, P)$:
$\emptyset$ is not an element of $\operatorname{refine}(S, P)$ due to the definition of intersection partition.

(iii)

To prove: $\operatorname{refine}(S, P)$ is a covering of $X$:
At first, $X \subseteq \bigcup_{A \in \operatorname{refine}(S, P)} A$ is shown, followed by $X \supseteq \bigcup_{A \in \operatorname{refine}(S, P)} A$.

For all $x \in X$ there are partition elements $A \in S$ and $B \in P$ which both contain $x$. Therefore, $x$ is in the intersection $A \cap B$ and there is a set $C$ in the intersection partition of $A$ and $B$ which also contains $x$. $C$ is an element of $\operatorname{refine}(S, P)$. Consequently, $x \in \bigcup_{D \in \operatorname{refine}(S, P)} D$.

On the other hand, for all $x \in \bigcup_{A \in \operatorname{refine}(S, P)} A$, there is a set $A \in \operatorname{refine}(S, P)$ which contains $x$. In turn, there are partition elements $A_S \in S$ and $A_P \in P$ for which $A$ is in their intersection partition. Because $x$ is in $A$, $x$ is also $A_S$ and $A_P$ and consequently also in $X$.

(iv)

To prove: $\operatorname{int}^\star _k(A) \cap \operatorname{int}^\star _k(B) = \emptyset$ for all sets $A \neq B$ of $\operatorname{refine}(S, P)$:
Let $k$ be the dimension of $X$ and $A$ and $B$ two different elements of $\operatorname{refine}(S, P)$. For $A \in \operatorname{refine}(S, P)$, there are partition elements $A_S \in S$ and $A_P \in P$ for which $A$ is in the intersection partition of $A_S$ and $A_P$. Similarly, for $B \in \operatorname{refine}(S, P)$, there are partition elements $B_S \in S$ and $B_P \in P$ for which $B$ is in the intersection partition of $B_S$ and $B_P$.

If $A_S = B_S$ and $A_P = B_P$, then $\operatorname{int}^\star _k(A) \cap \operatorname{int}^\star _k(B)$ is empty due to the definition of the intersection partition.

Otherwise, from Lemma A.1 and due to the assumption that ${\operatorname{DIM}}(A)$ and ${\operatorname{DIM}}(B)$ are less or equal to $k$ follows, that

$$\begin{multline} \operatorname{int}^\star _k(A) \cap \operatorname{int}^\star _... ...(S_A \cap S_B)) \cap \operatorname{int}^\star _k((P_A \cap P_B)) \end{multline}$$

However, $S$ and $P$ are manifold partitions and $\operatorname{int}^\star _k((S_A \cap S_B)) = \operatorname{int}^\star _k((P_A \cap P_B)) = \emptyset$.

$\qedsymbol$