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 xy-monotone polyhedral surface in 3D, called a 2.5D terrain.

Figure 1
Credit: de Berg et al

In this setting, the choice of an adequate triangulation turns out to be crucial, as can be seen in the following example from 1: 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 q 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.

Figure 2
Credit: de Berg et al.

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 flip2.

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 3 answered this question in the positive and showed a quadratic bound for the diameter. This was later shown to be tight, hence \Theta(n^2), by Hurtado et al. 4. In a higher dimension, Santos 5 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.

Credit: Bose & Hurtado
Credit: Bose & Hurtado

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 6 and Komuro 7 showed its linear size \Theta(n). For the labeled case, Sleator et al. 8 proved the diameter to be \Theta(n \log(n)).

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. 9.

Credit: David Orden
Credit: David Orden

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 10 and having diameter in O(n \log(n))11. 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 O(n \log(n))12.

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.

Credit: David Orden
Credit: David Orden

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 13, we answer the question in the positive for combinatorial 4-PPTs, showing a quadratic bound O(n^2) 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.

Figure 6
Credit: Aichholzer et al

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

Credit: Jannis Andrija Schnitzer's flickr
Credit: Jannis Andrija Schnitzer’s flickr

References

  1. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry, Algorithms and Applications. Springer-Verlag. DOI: 10.1007/978-3-540-77974-2
  2. Prosenjit Bose and Ferran Hurtado. Flips in planar graphs. Computational Geometry
    Volume 42, Issue 1, January 2009, Pages 60–80. DOI: 10.1016/j.comgeo.2008.04.001
  3. Charles L. Lawson. Transforming triangulations. Discrete Mathematics, Volume 3, Issue 4, 1972, Pages 365-372. DOI: 10.1016/0012-365X(72)90093-3
  4. Ferran Hurtado, Marc Noy, and Jorge Urrutia. Flipping Edges in Triangulations. Discrete and Computational Geometry. October 1999, Volume 22, Issue 3, pp 333-346. DOI: 10.1007/PL00009464
  5. Francisco Santos. A point set whose space of triangulations is disconnected. Journal of the American Mathematical Society. Volume 13, Number 3, Pages 611-637. DOI: 10.1090/S0894-0347-00-00330-1
  6. K. Wagner. Bemerkungen zum Vierfarbenproblem. Jahresbericht der Deutschen
    Mathematiker-Vereinigung 46 (1936) 26–32.
  7. H. Komuro. The diagonal flips of triangulations on the sphere. Yokohama Mathematical Journal, 44(2) (1997) 115–122.
  8. D. D. Sleator, R. E. Tarjan, and W. P. Thurston. Short encodings of evolving structures. SIAM Journal on Discrete Mathematics 5(3) (1992) 428–450. DOI: 10.1137/0405034
  9. Günter Rote, Francisco Santos, and Ileana Streinu. Pseudo-triangulations – a Survey. Contemporary mathematics 453 (2008), 343-410. DOI: 10.1090/conm/453/08807
  10. David Orden and Francisco Santos. The Polytope of Non-Crossing Graphs on a Planar Point Set. Discrete and Computational Geometry 33:275-305 (2005). DOI: 10.1007/s00454-004-1143-1
  11. S. Bereg. Transforming pseudo-triangulations. Information Processing Letters, 90(3) (2004)
    141-145. DOI:10.1016/j.ipl.2004.01.021
  12. O. Aichholzer, F. Aurenhammer, H. Krasser, and P. Braß. Pseudotriangulations from surfaces and a novel type of edge flip. SIAM Journal on Computing 32(6) (2003) 1621-1653. DOI: 10.1137/S0097539702411368
  13. O. Aichholzer, T. Hackl, D. Orden, A. Pilz, M. Saumell, and B. Vogtenhuber. Flips in combinatorial pointed pseudo-triangulations with face degree at most four. International Journal of Computational Geometry & Applications Vol. 24, No. 3 (2014) 197–224. DOI: 10.1142/S0218195914600036

Written by

1 comment

Leave a Reply

Your email address will not be published.Required fields are marked *