Jus*_* L. 8 language-agnostic algorithm math geometry topology
编辑 正如有人指出的那样,我正在寻找的实际上是最小化所有其他点之间的总测地距离的点
我的地图在地形上类似于吃豆人和小行星的地图.越过顶部会让你翘起到底部,经过左边会让你向右弯曲.
假设我在地图上有两个点(质量相同),我想找到它们的质心.我可以使用经典定义,它基本上是中点.
但是,让我们说这两点是在质量的两端.可以说,还有另一个质心,它是通过"环绕"包裹而形成的.基本上,它是与其他两个点等距的点,但是通过"环绕"边缘来链接.
例
b . O . . a . . O .
两点O.他们的"经典"中点/质心是标记的点a.然而,另一个中点也在b(b通过环绕绕两个点等距离).
在我的情况下,我想选择两点之间平均距离较低的那个.在这种情况下,a具有三个步骤的两个点之间的平均距离. b平均距离为两步.所以我会选择b.
解决两点情况的一种方法是简单地测试经典中点和最短环绕中点,并使用具有较短平均距离的中点.
然而!这不容易推广到3个点,或4个,或5个,或n个点.
有没有我可以用来找到这个的公式或算法？
(假设所有积分将永远是等质量的,我只能用"重心",因为它是我知道松散地描述我试图做的唯一项)
如果我的解释不清楚,我会尝试更好地解释它.
质心的概念是与仿射空间相关的概念。n 维环面没有仿射结构。
您想要的是一个能够最小化到所有其他点的（测地线）距离的点。
我建议如下：让 x_1...x_n 为 d 维环面（或用于此目的的任何其他度量空间）上的点的集合。
你的问题：
找到一个点 mu 使得 sum(dist(mu, x_k)^2) 最小。
在仿射欧几里得的情况下，您会得到通常的质心概念。
您可以使用共轭梯度算法来解决这个问题（例如，可能有更好的选择） ，该算法在这种情况下表现良好。请注意，您需要适度的 n（例如 n < 10^3），因为该算法在空间上需要 n^2，在时间上需要 n^3。
也许更适合的是 Levenberg-Marquardt 算法，它是为最小化平方和而定制的。
请注意，如果您有一个良好的初始猜测（例如，通常将点的质心视为 R^d 中的点而不是圆环），则该方法将收敛得更快。
编辑：如果 (x1...xd) 和 (y1...yd) 是圆环上的点，则距离由 dist(x, y)^2 = alpha1^2 + ... + alphad^2 给出
其中 alphai = min((xi - yi) mod 1, (yi - xi) mod 1)