We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds. Both can be viewed as providing the functionality of Fast Multipole Methods (FMMs), which have had a tremendous impact on efficient integration, but for non-Euclidean spaces. We focus on geometries induced by distributions of walk lengths between points (e.g., shortest-path distance). We provide an extensive theoretical analysis of our algorithms, obtaining new results in structural graph theory as a byproduct. We also perform exhaustive empirical evaluation, including on-surface interpolation for rigid and deformable objects (particularly for mesh-dynamics modeling), Wasserstein distance computations for point clouds, and the Gromov-Wasserstein variant.

翻译：我们提出了两类新算法，用于在编码点云的图形上进行高效场积分。第一类算法，SeparatorFactorization（SF），利用点云网格图的有界亏格，而第二类算法，RFDiffusion（RFD），则使用流行的ε- 最近邻图表示法来表示点云。它们都可以被视为为非欧几里得空间提供快速多极方法（FMM）的功能。我们专注于由点之间行走长度分布（例如，最短路径距离）产生的几何形状。我们提供了广泛的理论分析，作为副产品，获得了结构图论的新结果。我们还进行了详尽的经验证明，包括对刚性和可变形物体进行表面插值（特别是用于网格动态建模），计算点云的Wasserstein距离以及Gromov-Wasserstein变量。