Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914352953556992 |
|---|---|
| author | Dorfer, Joseph |
| author_facet | Dorfer, Joseph |
| contents | Flips in triangulations of convex polygons arise in many different settings. They are isomorphic to rotations in binary trees, define edges in the 1-skeleton of the Associahedron and cover relations in the Tamari Lattice.
The complexity of determining the minimum number of flips that transform one triangulation of a convex point set into another remained a tantalizing open question for many decades. We settle this question by proving that computing shortest flip sequences between triangulations of convex polygons, and therefore also computing the rotation distance of binary trees, is NP-hard.
For our proof we develop techniques for flip sequences of triangulations whose counterparts were introduced for the study of flip sequences of non-crossing spanning trees by Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber~[SODA25] and Bjerkevik, Dorfer, Kleist, Ueckerdt, and Vogtenhuber~[SoCG26]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_22874 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete Dorfer, Joseph Computational Geometry Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics Flips in triangulations of convex polygons arise in many different settings. They are isomorphic to rotations in binary trees, define edges in the 1-skeleton of the Associahedron and cover relations in the Tamari Lattice. The complexity of determining the minimum number of flips that transform one triangulation of a convex point set into another remained a tantalizing open question for many decades. We settle this question by proving that computing shortest flip sequences between triangulations of convex polygons, and therefore also computing the rotation distance of binary trees, is NP-hard. For our proof we develop techniques for flip sequences of triangulations whose counterparts were introduced for the study of flip sequences of non-crossing spanning trees by Bjerkevik, Kleist, Ueckerdt, and Vogtenhuber~[SODA25] and Bjerkevik, Dorfer, Kleist, Ueckerdt, and Vogtenhuber~[SoCG26]. |
| title | Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete |
| topic | Computational Geometry Computational Complexity Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2602.22874 |