在这篇文章中，我们介绍了GenusSink，这是一类新的近似广义Sinkhorn算法，适用于有界属（例如平面）图的最短路径距离成本，提供近线性的：
- 预处理
- 迭代步骤
- 最终传输计划矩阵查询
并且内存使用也接近线性。GenusSink处理的图特别包括平面图和近似3D对象的有界属网格。该算法通过利用图的分离器分解、计算几何技术以及关于通用距离矩阵的快速矩阵-向量乘法的新结果，解决了其暴力算法的总平方时间复杂度，特别是使用傅里叶分析和低位移秩理论。
该算法受到图论中关于用小树宽度度量近似有界属度量的最新突破的启发。图中心化的方法使我们能够针对最优传输问题，定义在由加权图近似的流形上的相应分布，成本函数由测地线距离给出。我们对GenusSink进行了严格的理论分析，提供了实际实现，利用了本文中新引入的分离图场积分器（S-GFIs）数据结构，并进行了实证验证。
GenusSink提供的计算精度比其他高效Sinkhorn算法高出几个数量级，同时仍然保证与基线相比的显著计算改进。作为所开发方法的副产品，我们展示了GenusSink在树宽为$O(\log\log(n))$（例如树）的$n$个顶点图上与暴力测地线Sinkhorn算法是\textbf{数值等价}的。
博主点评： GenusSink算法通过创新的图形处理和数学理论，显著提升了广义Sinkhorn算法在有界属图上的效率。通过结合几何技术与傅里叶分析，该算法不仅在理论上有重要意义，也为实际应用提供了更高的计算精度，展示了图论与计算几何的深度交叉潜力。