algorithm - "Center of Mass"在环形包裹 map 上的一组点之间，最小化到所有点的平均距离

Question

编辑 正如有人指出的那样，我正在寻找的实际上是最小化所有其他点之间的总测地线距离的点

---

我的 map 在地形上与《吃 bean 人》和《小行星》中的 map 相似。越过顶部将使您进入底部，越过左侧将使您进入右侧。

假设我在 map 上有两个点(质量相同)，我想找到它们的质心。我可以使用经典定义，它基本上是中点。

但是，假设这两个点位于质量的两端。可以说，还有另一个重心是通过“环绕”形成的。基本上，它是与其他两个点等距的点，但通过“环绕”边缘连接。

例子

b . O . . a . . O .

两点O。它们的“经典”中点/质心是标记为 a 的点。然而，另一个中点也在 b 处(b 与两点等距，环绕)。

在我的情况下，我想选择两点之间平均距离较小的那个。在这种情况下，a 具有三步两点之间的平均距离。 b 的平均距离为两步。所以我会选择 b。

解决两点情况的一种方法是简单地测试经典中点和最短环绕中点，并使用平均距离较短的中点。

但是!这不容易概括为 3 点、4 点、5 点或 n 点。

有没有我可以用来找到它的公式或算法？

(假设所有点的质量始终相同。我只使用“质心”，因为这是我所知道的唯一可以粗略描述我正在尝试做的事情的术语)

如果我的解释不清楚，我会尽力解释得更好。

Answer 1

质心的概念是与仿射空间相关的概念。 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) 是圆环上的点，则距离由下式给出距离(x，y)^2 = alpha1^2 + ... + alphaad^2

其中 alphai = min((xi - yi) mod 1, (yi - xi) mod 1)