A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes
A Polynomial Time Algorithm to Compute Geodesics in CAT(0) Cubical Complexes
复制标题
计算 CAT(0) 立方复形中测地线的多项式时间算法
DOI：
10.1007/s00454-019-00154-2
复制
发表时间：
2021
影响因子：
0.8
通讯作者：
Koyo Hayashi
中科院分区：
文献类型：
--
作者：
Koyo Hayashi;Ken-ichi Kawarabayashi;Koyo Hayashi
给出了计算一般维CAT(0)立方复数中测地线的第一个多项式时间算法。该算法是一种简单的迭代方法，使用Owen和Provan的算法(IEEE/ACM Trans Comput Biol Bioinform 8(1)：2-13,2011)作为子程序来更新连接两点的路径的断点。我们的算法适用于任何CAT(0)空间中可以计算两个闭合点之间的测地线的任何路径，而不限于CAT(0)三次复形。
This paper presents the first polynomial time algorithm to compute geodesics in a CAT(0) cubical complex in general dimension. The algorithm is a simple iterative method to update breakpoints of a path joining two points using Owen and Provan’s algorithm (IEEE/ACM Trans Comput Biol Bioinform 8(1):2–13, 2011) as a subroutine. Our algorithm is applicable to any path in any CAT(0) space in which geodesics between two close points can be computed, not limited to CAT(0) cubical complexes.