Flip me to the moon

This post is dedicated to the memory of Professor Ferran Hurtado, inspirational friend and colleague.

Triangulations are extremely useful in computer graphics, with terrain modeling being an outstanding example: A mesh of points in 2D is triangulated and then the triangulation is lifted to obtain an -monotone polyhedral surface in 3D, called a 2.5D terrain.

In this setting, the choice of an adequate triangulation turns out to be crucial, as can be seen in the following example from ¹: In the figure, both pictures show a set of points in 2D with a label indicating the height of each point. On one hand, the triangulation in the left picture suggests that the height of the point should be 985, with the sample points taken from a mountain ridge. On the other hand, by exchanging a single edge, the triangulation in the right picture introduces a narrow valley cutting through the mountain ridge.

The triangulation in the left picture, which is most likely to reflect the actual landscape, is actually a Delaunay triangulation, in which construction plays a key role that operation of exchanging a single edge, called edge flip².

One of the most natural and important questions about flips is whether, given any pair of triangulations, it is possible to transform one into the other by a finite sequence of flips. For a set of n points in 2D sets as above, Lawson ³ answered this question in the positive and showed a quadratic bound for the diameter. This was later shown to be tight, hence , by Hurtado et al. ⁴. In a higher dimension, Santos ⁵ found a point configuration in 6D whose space of triangulations is disconnected.

The abstract setting, instead of the geometric one, can also be considered. The notion of geometric embedding is replaced by that of combinatorial embedding, defined by a clockwise order of the edges around each vertex. Combinatorial triangulations admit flips which are not possible in the geometric setting, as shown in the following example.

This is a labeled combinatorial triangulation, since vertices are identified and distinguished by labels. Furthermore, unlabeled combinatorial triangulations can also be considered. In both cases, the flip graph turns out to be connected as well. For the unlabeled case, connectedness was proved by Wagner ⁶ and Komuro ⁷ showed its linear size . For the labeled case, Sleator et al. ⁸ proved the diameter to be .

Triangulations have a natural generalization in pseudo-triangulations. They have become a popular structure in Computational Geometry within the last two decades, with applications in, e.g., rigidity theory and motion planning. More information can be found in the post “Triangulations are rigid. You can do better using pseudo-triangles” and in the survey by Rote et al. ⁹.

As shown in the picture above, one of the properties naturally generalized from triangulations to pseudo-triangulations is the existence of edge flips, with the graph of flips being connected as well ¹⁰ and having diameter in ¹¹. It is interesting to note that triangulations are a particular type of pseudo-triangulations, actually the ones with the largest number of edges.

On the contrary, the pseudo-triangulations with fewest edges are the so-called pointed pseudo-triangulations (PPTs), which turn out to be those in which every vertex is incident to an angle of size at least \pi (like those in the upper part of the previous figure). The subgraph induced by these PPTs in the flip graph of general pseudo-triangulations turns out to be connected as well, with a diameter also in ¹².

Particularizing further, there is an interesting class inside that of PPTs: The so-called 4-PPTs, in which the faces are either triangles or non-convex quadrilaterals (let us call them moons). See the following picture for an example. These 4-PPTs can be considered the “PPTs being closest to a triangulation”, since triangles are the smallest convex polygons and moons are the smallest non-convex polygons.

Of course, these 4-PPTs also admit flips: Among others, the reader can check that the edges of triangles are flippable (as long as they are not part of the boundary). And this leads to one of the intriguing open questions in Discrete and Computational Geometry: Is the flip graph of 4-PPTs connected?

In a recent paper ¹³, we answer the question in the positive for combinatorial 4-PPTs, showing a quadratic bound for the diameter, even in the case of labeled vertices with fixed outer face.

Unfortunately, we found examples for which the combinatorial flips are not possible in the geometric setting, since they would need different geometric embeddings. The following picture shows an example.

Hence, the connectedness of the flip graph for geometric 4-PPTs remains as a very interesting open problem.