论文标题
A $ O（3.82^k）$ time fpt算法，用于凸面翻转距离
An $O(3.82^k)$ Time FPT Algorithm for Convex Flip Distance
论文作者
论文摘要
让$ p $是飞机上的凸多边形，让$ t $为$ p $的三角剖分。如果两个三角形共享$ t $，则$ t $中的边缘$ e $称为对角线。对角线$ e $的翻转是删除$ e $的操作，并添加了相反的对角线，从而从$ t $中获得了新的三角剖分。 $ p $的两个三角剖分之间的翻转距离是将一个三角剖分转换为另一个三角形所需的最小翻转数。凸面上的距离问题询问两个给定的三角形$ p $之间的翻转距离最多是$ k $，对于某些给定参数$ k $。 我们提出了一种fpt算法，用于凸面上的距离问题，该问题在时间$ o（3.82^k）$中运行，并使用多项式空间，其中$ k $是翻转的数量。该算法显着改善了该问题的先前最佳FPT算法。
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 $O(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.
