3.2.1 Topological Operations

Figure 3.4: Edge flipping operation for triangles

The edge shared by the triangles is flipped to the other diagonal of the quadrilateral which is formed by the union of two triangles. The flipping operation requires the quadrilateral to be convex, otherwise the underlying space changes. In this particular example, the triangles are Delaunay (cf. Section 2.3) after the flipping operation is applied.

Topological operations are operations which do not insert, delete, or move any vertices. The most popular topological operations are flips, where a number of neighboring cells are replaced by another configuration of cells. For example, an edge flip, visualized in Figure 3.4, is an operation, where two triangles sharing one edge are replaced by two different triangles. Flip operations for 2D triangle meshes have a special role as they can make any mesh Delaunay. It can be shown, that for a triangulation every edge $E$ is either locally Delaunay or $E$ is flippable and the flipped edge is locally Delaunay [127]. It can also be shown, that the algorithm which recursively flips every edge which is not locally Delaunay terminates and therefore results in a Delaunay mesh [127]. The 3D extension of the 2D flips are called bistellar flips [50]. However, bistellar flips are fairly complex and cannot be applied to all configurations of neighboring tetrahedrons. Additionally, recursively performing bistellar flips on tetrahedral meshes only results in a mesh which is Delaunay for edge-protected PLCs [67]. However, it has been proven, that there are algorithms using flip operations which result in a simplex Delaunay mesh for arbitrary dimensions $n$ [136]. Flip operations can be defined for arbitrary element types by using the projections of an element of the same type with one dimension higher [83].