4.4 Template-Aware Delaunay

The Delaunay property (cf.Section 2.3) is a powerful property for simplex meshes. It is therefore of interest to investigate this property for templated meshes as well.

Figure 4.12: Issues with the Delaunay property of templated meshes

Although the mesh template $X_1$ is Delaunay, the structure instance on the right is not because of the two triangles visualized in red.

A simplex element $S$, which is Delaunay in the structure instance of a templated mesh, is also Delaunay in all of its mesh templates. However, the converse is generally not true. A simplex element $S \in {\Gamma}_i$, which is Delaunay in the mesh template $T_{i,j}(E)$, is not necessarily Delaunay in the structure instance as visualized in Figure 4.12. As shown in Lemma 2.5, global locally Delaunay is equivalent to global Delaunay. Therefore, elements, which are not locally Delaunay in the structure instance of a templated mesh with all mesh templates being Delaunay, have to be in an instance interface. To identify these elements, the locally Delaunay property is defined for templated meshes.

With this definition, the following Lemma can be formulated.

Lemma 5 (Template-aware Delaunay Lemma)   Let ${\Gamma}$ be a templated mesh. If all facets of all mesh templates of ${\Gamma}$ are template-aware locally Delaunay, then ${\operatorname{AT}}({\Gamma})$ is Delaunay.

Proof. Every facet in the structure instance is locally Delaunay because of the template-aware locally Delaunay property of every template facet. Therefore, the structure instance is Delaunay due to Lemma 2.5. $\qedsymbol$

In other words, if every mesh template of a templated mesh is Delaunay and every template boundary element is template-aware locally Delaunay, then ${\operatorname{AT}}({\Gamma})$ is Delaunay. An algorithm which adapts a templated mesh to be Delaunay is presented in Section 5.2.5.