Flip distance

In discrete mathematics and theoretical computer science, the flip distance between two triangulations of the same point set is the number of flips required to transform one triangulation into another. A flip removes an edge between two triangles in the triangulation and then adds the other diagonal in the edge's enclosing quadrilateral, forming a different triangulation of the same point set.

This problem is known to be NP-hard. However, the computational complexity of determining the flip distance between convex polygons, a special case of this problem, is unknown. Computing the flip distance between convex polygon triangulations is also equivalent to rotation distance, the number of rotations required to transform one binary tree into another.

Definition[edit]

Given a family of triangulations of some geometric object, a flip is an operation that transforms one triangulation to another by removing an edge between two triangles and adding the opposite diagonal to the resulting quadrilateral. The flip distance between two triangulations is the minimum number of flips needed to transform one triangulation into another.^[1] It can also be described as the shortest path distance in a flip graph, a graph that has a vertex for each triangulation and an edge for each flip between two triangulations.^[1] Flips and flip distances can be defined in this way for several different kinds of triangulations, including triangulations of sets of points in the Euclidean plane, triangulations of polygons, and triangulations of abstract manifolds.^[2]

Feasiblity[edit]

The flip distance is well-defined only if any triangulation can be converted to any other triangulation via a sequence of flips. An equivalent condition is that the flip graph must be connected.^[3]

In 1936, Klaus Wagner showed that maximal planar graphs on a sphere can be transformed to any other maximal planar graph with the same vertices through flipping.^[4] A. K. Dewdney generalized this result to triangulations on the surface of a torus while Charles Lawson to triangulations of a point set on a 2-dimensional plane.^[2]^[5]

For triangulations of a point set in dimension 5 or above, there exists examples where the flip graph is disconnected and a triangulation cannot be obtained from other triangulations via flips.^[6]^[3] Whether all flip graphs of finite 3- or 4-dimensional point sets are connected is an open problem.^[7]

Diameter of the flip graph[edit]

The maximum number of flips required to transform a triangulation into another is the diameter of the flip graph. The diameter of the flip graph of a convex $n$ -gon has been obtained by Daniel Sleator, Robert Tarjan, and William Thurston^[8] when $n$ is sufficiently large and by Lionel Pournin for all $n$ . This diameter is equal to $2n-10$ when $n\geq 13$ .^[9]

The diameter of other flip graphs has been studied. For instance Klaus Wagner provided a quadratic upper bound on the diameter of the flip graph of a set of $n$ unmarked points on the sphere.^[4] The current upper bound on the diameter is $5.2n-33.6$ ,^[10] while the best-known lower bound is $7n/3+\Theta (1)$ .^[11] The diameter of the flip graphs of arbitrary topological surfaces with boundary has also been studied and their exact value is known in several cases.^[12]^[13]^[14]

Equivalence with other problems[edit]

The flip distance between triangulations of a convex polygon is equivalent to the rotation distance between two binary trees.^[8]

Computational complexity[edit]

Unsolved problem in computer science:

What is the complexity of computing the flip distance between two triangulations of a convex polygon?

(more unsolved problems in computer science)

Computing the flip distance between triangulations of a point set is both NP-complete and APX-hard.^[15]^[16] However, it is fixed-parameter tractable (FPT), and several FPT algorithms that run in exponential time have been proposed.^[17]^[18]

Computing the flip distance between triangulations of a simple polygon is also NP-hard.^[19]

The complexity of computing the flip distance between triangulations of a convex polygon remains an open problem.^[20]

Algorithms[edit]

Let $n$ be the number of points in the point set and $k$ be the flip distance. The current best FPT algorithm runs in $O(n+k\cdot 32^{k})$ .^[17] A faster FPT algorithm exists for the flip distance between convex polygon triangulations; it has time complexity $O(3.82^{k})$ ^[20]

If no five points of a point set form an empty pentagon, there exists a $O(n^{2})$ algorithm for the flip distance between triangulations of this point set.^[1]

References[edit]

^ ^a ^b ^c Eppstein, David (2010). "Happy endings for flip graphs". Journal of Computational Geometry. 1 (1): Vol. 1 No. 1 (2010). doi:10.20382/JOCG.V1I1A2.
^ ^a ^b Dewdney, A.K. (1973). "Wagner's theorem for Torus graphs". Discrete Mathematics. 4 (2). Elsevier BV: 139–149. doi:10.1016/0012-365x(73)90076-9. ISSN 0012-365X.
^ ^a ^b Santos, Francisco (2005-04-02). "Non-connected toric Hilbert schemes". Mathematische Annalen. 332 (3). Springer Science and Business Media LLC: 645–665. arXiv:math/0204044. doi:10.1007/s00208-005-0643-5. ISSN 0025-5831.
^ ^a ^b Wagner, K. (1936). "Bemerkungen zum Vierfarbenproblem". Jahresbericht der Deutschen Mathematiker-Vereinigung. 46: 26–32. ISSN 0012-0456.
^ Lawson, Charles L. (1972). "Transforming triangulations". Discrete Mathematics. 3 (4). Elsevier BV: 365–372. doi:10.1016/0012-365x(72)90093-3. ISSN 0012-365X.
^ Santos, Francisco (2000). "A Point Set Whose Space of Triangulations is Disconnected". Journal of the American Mathematical Society. 13 (3). American Mathematical Society: 611–637. doi:10.1090/S0894-0347-00-00330-1. hdl:10902/2584. ISSN 0894-0347. JSTOR 2646121.
^ De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Vol. 25. Springer.
^ ^a ^b Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3). American Mathematical Society (AMS): 647–681. doi:10.1090/s0894-0347-1988-0928904-4. ISSN 0894-0347.
^ Pournin, Lionel (2014), "The diameter of associahedra", Advances in Mathematics, 259: 13–42, arXiv:1207.6296, doi:10.1016/j.aim.2014.02.035, MR 3197650
^ Bose, Prosenjit; Verdonschot, Sander (2012). "A History of Flips in Combinatorial Triangulations". Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 29–44. arXiv:1206.0303. doi:10.1007/978-3-642-34191-5_3. ISBN 978-3-642-34190-8. ISSN 0302-9743. S2CID 18896454.
^ Frati, Fabrizio (2017). "A Lower Bound on the Diameter of the Flip Graph". Electronic Journal of Combinatorics. 24 (1): P1.43. arXiv:1508.03473. doi:10.37236/5489.
^ Parlier, Hugo; Pournin, Lionel (2017). "Flip-graph moduli spaces of filling surfaces". Journal of the European Mathematical Society. 19 (9): 2697–2737. arXiv:1407.1516. doi:10.4171/JEMS/726.
^ Parlier, Hugo; Pournin, Lionel (2018). "Modular flip-graphs of one holed surfaces". European Journal of Combinatorics. 67: 158–173. arXiv:1510.07664. doi:10.1016/j.ejc.2017.07.003.
^ Parlier, Hugo; Pournin, Lionel (2018). "Once punctured disks, non-convex polygons, and pointihedra". Annals of Combinatorics. 22 (3): 619–640. arXiv:1602.04576. doi:10.1007/s00026-018-0393-1.
^ Lubiw, Anna; Pathak, Vinayak (2015). "Flip distance between two triangulations of a point set is NP-complete". Computational Geometry. 49. Elsevier BV: 17–23. arXiv:1205.2425. doi:10.1016/j.comgeo.2014.11.001. ISSN 0925-7721.
^ Pilz, Alexander (2014). "Flip distance between triangulations of a planar point set is APX-hard". Computational Geometry. 47 (5). Elsevier BV: 589–604. arXiv:1206.3179. doi:10.1016/j.comgeo.2014.01.001. ISSN 0925-7721.
^ ^a ^b Feng, Qilong; Li, Shaohua; Meng, Xiangzhong; Wang, Jianxin (2021). "An fpt2 FPT algorithm for the flip distance problem". Information and Computation. 281. Elsevier BV: 104708. arXiv:1910.06185. doi:10.1016/j.ic.2021.104708. ISSN 0890-5401.
^ Kanj, Iyad; Sedgwick, Eric; Xia, Ge (2017-02-10). "Computing the Flip Distance Between Triangulations". Discrete & Computational Geometry. 58 (2). Springer Science and Business Media LLC: 313–344. arXiv:1407.1525. doi:10.1007/s00454-017-9867-x. ISSN 0179-5376.
^ Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alexander (2015-06-11). "Flip Distance Between Triangulations of a Simple Polygon is NP-Complete". Discrete & Computational Geometry. 54 (2). Springer Science and Business Media LLC: 368–389. arXiv:1209.0579. doi:10.1007/s00454-015-9709-7. ISSN 0179-5376.
^ ^a ^b Li, Haohong; Xia, Ge (2023). "An 𝒪(3.82^k) Time FPT Algorithm for Convex Flip Distance". Schloss Dagstuhl - Leibniz-Zentrum für Informatik. doi:10.4230/LIPICS.STACS.2023.44. Retrieved 2023-11-08.

[eppstein-1] Eppstein, David (2010). "Happy endings for flip graphs". Journal of Computational Geometry. 1 (1): Vol. 1 No. 1 (2010). doi:10.20382/JOCG.V1I1A2.

[dewdney-2] Dewdney, A.K. (1973). "Wagner's theorem for Torus graphs". Discrete Mathematics. 4 (2). Elsevier BV: 139–149. doi:10.1016/0012-365x(73)90076-9. ISSN 0012-365X.

[santos2-3] Santos, Francisco (2005-04-02). "Non-connected toric Hilbert schemes". Mathematische Annalen. 332 (3). Springer Science and Business Media LLC: 645–665. arXiv:math/0204044. doi:10.1007/s00208-005-0643-5. ISSN 0025-5831.

[wagner-4] Wagner, K. (1936). "Bemerkungen zum Vierfarbenproblem". Jahresbericht der Deutschen Mathematiker-Vereinigung. 46: 26–32. ISSN 0012-0456.

[lawson-5] Lawson, Charles L. (1972). "Transforming triangulations". Discrete Mathematics. 3 (4). Elsevier BV: 365–372. doi:10.1016/0012-365x(72)90093-3. ISSN 0012-365X.

[santos-6] Santos, Francisco (2000). "A Point Set Whose Space of Triangulations is Disconnected". Journal of the American Mathematical Society. 13 (3). American Mathematical Society: 611–637. doi:10.1090/S0894-0347-00-00330-1. hdl:10902/2584. ISSN 0894-0347. JSTOR 2646121.

[loera-7] De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Vol. 25. Springer.

[stt-8] Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988). "Rotation distance, triangulations, and hyperbolic geometry". Journal of the American Mathematical Society. 1 (3). American Mathematical Society (AMS): 647–681. doi:10.1090/s0894-0347-1988-0928904-4. ISSN 0894-0347.

[pournin-9] Pournin, Lionel (2014), "The diameter of associahedra", Advances in Mathematics, 259: 13–42, arXiv:1207.6296, doi:10.1016/j.aim.2014.02.035, MR 3197650

[bv-10] Bose, Prosenjit; Verdonschot, Sander (2012). "A History of Flips in Combinatorial Triangulations". Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 29–44. arXiv:1206.0303. doi:10.1007/978-3-642-34191-5_3. ISBN 978-3-642-34190-8. ISSN 0302-9743. S2CID 18896454.

[frati-11] Frati, Fabrizio (2017). "A Lower Bound on the Diameter of the Flip Graph". Electronic Journal of Combinatorics. 24 (1): P1.43. arXiv:1508.03473. doi:10.37236/5489.

[pp2017-12] Parlier, Hugo; Pournin, Lionel (2017). "Flip-graph moduli spaces of filling surfaces". Journal of the European Mathematical Society. 19 (9): 2697–2737. arXiv:1407.1516. doi:10.4171/JEMS/726.

[pp2018a-13] Parlier, Hugo; Pournin, Lionel (2018). "Modular flip-graphs of one holed surfaces". European Journal of Combinatorics. 67: 158–173. arXiv:1510.07664. doi:10.1016/j.ejc.2017.07.003.

[pp2018b-14] Parlier, Hugo; Pournin, Lionel (2018). "Once punctured disks, non-convex polygons, and pointihedra". Annals of Combinatorics. 22 (3): 619–640. arXiv:1602.04576. doi:10.1007/s00026-018-0393-1.

[lp-15] Lubiw, Anna; Pathak, Vinayak (2015). "Flip distance between two triangulations of a point set is NP-complete". Computational Geometry. 49. Elsevier BV: 17–23. arXiv:1205.2425. doi:10.1016/j.comgeo.2014.11.001. ISSN 0925-7721.

[pilz-16] Pilz, Alexander (2014). "Flip distance between triangulations of a planar point set is APX-hard". Computational Geometry. 47 (5). Elsevier BV: 589–604. arXiv:1206.3179. doi:10.1016/j.comgeo.2014.01.001. ISSN 0925-7721.

[fpt2-17] Feng, Qilong; Li, Shaohua; Meng, Xiangzhong; Wang, Jianxin (2021). "An fpt2 FPT algorithm for the flip distance problem". Information and Computation. 281. Elsevier BV: 104708. arXiv:1910.06185. doi:10.1016/j.ic.2021.104708. ISSN 0890-5401.

[fpt1-18] Kanj, Iyad; Sedgwick, Eric; Xia, Ge (2017-02-10). "Computing the Flip Distance Between Triangulations". Discrete & Computational Geometry. 58 (2). Springer Science and Business Media LLC: 313–344. arXiv:1407.1525. doi:10.1007/s00454-017-9867-x. ISSN 0179-5376.

[amp-19] Aichholzer, Oswin; Mulzer, Wolfgang; Pilz, Alexander (2015-06-11). "Flip Distance Between Triangulations of a Simple Polygon is NP-Complete". Discrete & Computational Geometry. 54 (2). Springer Science and Business Media LLC: 368–389. arXiv:1209.0579. doi:10.1007/s00454-015-9709-7. ISSN 0179-5376.

[fpt-convex-20] Li, Haohong; Xia, Ge (2023). "An 𝒪(3.82^k) Time FPT Algorithm for Convex Flip Distance". Schloss Dagstuhl - Leibniz-Zentrum für Informatik. doi:10.4230/LIPICS.STACS.2023.44. Retrieved 2023-11-08.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]