Bistellar Flips
From VoroWiki
A bistellar flip is a local topological operation that modifies the configuration of adjacent triangles in a triangulation. As shown in the figure, a four-sided convex polygon abcd can be triangulated in two different ways. A flip (called a flip22 in 2D) is the operation that will transform one configuration into the other one -- a flip of the diagonal (also called a swap) is performed.
Observe that only one of the two triangulation of the four-sided convex polygon is a Delaunay triangulation, and that a flip22 performed on the non-Delaunay configuration yields a triangulation where both triangle have an empty circumcircle. The empty circumcircle criterion also guarantees that the triangles are as equilateral as possible.
For the insertion and deletion of points in a DT, we also need other kinds of flips: the flip13 and the flip31 (the numbers refer to the number of triangles before and after the flip). The former inserts a new point in a triangle (splitting it into 3 new triangles), and the latter deletes a point having 3 incident triangles, yielding a single triangle.
Three-dimensional Bistellar Flips
A three-dimensional bistellar flip is a local operation that modifies the configuration of some adjacent tetrahedra. Consider the set S = {a,b,c,d,e} of points in general position in 
and its convex hull conv(S). There exist two possible configurations, as shown in the figure on the left:
- the five points of S lie on the boundary of conv(S). According to Lawson (1986)[1], there are exactly two ways to tetrahedralize such a polyhedron: either with two or three tetrahedra. In the first case, the two tetrahedra share a triangular face bcd, and in the latter case the three tetrahedra all have a common edge ae.
- one point e of S does not lie on the boundary of conv(S), thus conv(S) forms a tetrahedron. The only way to tetrahedralize S is with four tetrahedra all incident to e.
Based on these two configurations, four types of flips in can be described: flip23, flip32, flip14 and flip41. When S is in the first configuration, two types of flips are possible: a flip23 is the operation that transforms one tetrahedralization of two tetrahedra into another one with three tetrahedra; and a flip32 is the inverse operation. If S is tetrahedralized with two tetrahedra and the triangular face bcd is not locally Delaunay, then a flip23 will create three tetrahedra whose faces are locally Delaunay. A flip14 refers to the operation of inserting a vertex inside a tetrahedron, and splitting it into four tetrahedra; and a flip41 is the inverse operation that deletes a vertex.
Bistellar flips do not always apply to adjacent tetrahedra (Joe, 1989)[2]. For example, in the figure describing the flips in 3D (a), a flip23 is possible on the two adjacent tetrahedra abcd and bcde if and only if the line ae passes through the triangular face bcd (which also means that the union of abcd and bcde is a convex polyhedron). If not, then a flip32 is possible if and only if there exists in the tetrahedralization a third tetrahedron adjacent to both abcd and bcde.
