2026-07-21T14:13:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17696 2024-03-06T11:00:20Z ddc:004 open_access

An 𝒪(3.82^k) Time FPT Algorithm for Convex Flip Distance Li, Haohong Xia, Ge Flip distance Rotation distance Triangulations Exact algorithms Parameterized complexity Let P be a convex polygon in the plane, and let T be a triangulation of P. An edge e in T is called a diagonal if it is shared by two triangles in T. A flip of a diagonal e is the operation of removing e and adding the opposite diagonal of the resulting quadrilateral to obtain a new triangulation of P from T. The flip distance between two triangulations of P is the minimum number of flips needed to transform one triangulation into the other. The Convex Flip Distance problem asks if the flip distance between two given triangulations of P is at most k, for some given parameter k ∈ ℕ. We present an FPT algorithm for the Convex Flip Distance problem that runs in time 𝒪(3.82^k) and uses polynomial space, where k is the number of flips. This algorithm significantly improves the previous best FPT algorithms for the problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haohong Li and Ge Xia 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.44 urn:nbn:de:0030-drops-176965 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.44 eng https://creativecommons.org/licenses/by/4.0/legalcode