Flip distance: Difference between revisions
PetraMagna (talk | contribs) new article; definition section is copied from rotation distance; feasibility section is (partly) copied from flip graph; see their history pages for attribution |
(No difference)
|
Revision as of 02:02, 8 November 2023
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
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. 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. 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.
Feasiblity
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.
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.[1] 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][3]
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.[4][5] Whether all flip graphs of finite 3- or 4-dimensional point sets are connected is an open problem.[6]
Diameter of the flip graph
Given a point set of n points, the maximum number of flips required to transform a triangulation into another is the diameter of the flip graph. Wagner's 1936 paper provided a quadratic upper bound, with a 1997 paper by Komuro improving this bound to a linear one. The current upper bound on the diameter is , while the lower bound is .[7][8]
Equivalence with other problems
The flip distance between triangulations of a convex polygon is equivalent to the rotation distance between two binary trees.[9]
Computational complexity
What is the complexity of computing the flip distance between two triangulations of a convex polygon?
Computing the flip distance between triangulations of a point set is both NP-complete and APX-hard.[10][11] However, it is fixed-parameter tractable (FPT), and several FPT algorithms that run in exponential time have been proposed.[12][13]
Computing the flip distance between triangulations of a simple polygon is also NP-hard.[14]
The complexity of computing the flip distance between triangulations of a convex polygon remains an open problem. This special case of flip distance is possibly an NP-intermediate problem.
See also
References
- ^ Wagner, Klaus (1936), "Bemerkungen zum Vierfarbenproblem", Jahresbericht der Deutschen Mathematiker-Vereinigung, 46: 26–32
- ^ 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.
- ^ Lawson, Charles L. (1972), "Transforming triangulations", Discrete Mathematics, 3: 365–372, doi:10.1016/0012-365X(72)90093-3, MR 0311491
- ^ Santos, Francisco (2000), "A point set whose space of triangulations is disconnected", Journal of the American Mathematical Society, 13: 611–637, doi:10.1090/S0894-0347-00-00330-1, MR 1758756
- ^ Santos, Francisco (2005), "Non-connected toric Hilbert schemes", Mathematische Annalen, 332: 645–665, arXiv:math/0204044, doi:10.1007/s00208-005-0643-5, MR 2181765
- ^ 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.
- ^ Bose, Prosenjit; Verdonschot, Sander (2012). "A History of Flips in Combinatorial Triangulations". Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. p. 29–44. doi:10.1007/978-3-642-34191-5_3. ISBN 978-3-642-34190-8. ISSN 0302-9743.
- ^ Bose, Prosenjit; Jansens, Dana; van Renssen, André; Saumell, Maria; Verdonschot, Sander (2014). "Making triangulations 4-connected using flips". Computational Geometry. 47 (2). Elsevier BV: 187–197. doi:10.1016/j.comgeo.2012.10.012. ISSN 0925-7721.
- ^ 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.
- ^ Lubiw, Anna; Pathak, Vinayak (2015). "Flip distance between two triangulations of a point set is NP-complete". Computational Geometry. 49. Elsevier BV: 17–23. 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. doi:10.1016/j.comgeo.2014.01.001. ISSN 0925-7721.
- ^ Feng, Qilong; Li, Shaohua; Meng, Xiangzhong; Wang, Jianxin (2021). "An improved FPT algorithm for the flip distance problem". Information and Computation. 281. Elsevier BV: 104708. 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. 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. doi:10.1007/s00454-015-9709-7. ISSN 0179-5376.