在d维空间中，找出n个点的直径。

Question

我想要找到128维空间中两个点集的直径。第一个点集有10000个点，第二个有1000000个点。因此我希望能够采用比O(n²)更好的算法来解决问题。该算法可以处理任意数量的点和维度，但目前我特别关心这两个特定的数据集。

我非常关注速度而不是精确度，因此基于这篇文章，我将通过计算每个坐标的最小值和最大值来找到（近似的）点集的边界框，因此时间复杂度为O(n*d)。然后，如果我找到了这个盒子的直径，问题就解决了。

在三维情况下，我可以找到一侧的直径，因为我知道两条边，然后可以对垂直于这侧的另一条边应用勾股定理。然而，我不确定这种方法是否适用于d维，并且我无法看出如何将其推广到d维。

有一个有趣的答案在这里，但它似乎仅适用于三维，并且我想要一种d维的方法。

有趣的论文：计算高维欧几里得空间中点集直径的方法。 链接。然而，在此阶段实施该算法对我来说似乎太过复杂。

- gsamaras

---

通用解决方案需要计算凸包。https://dev59.com/T3E85IYBdhLWcg3whD7k - John Henckel

Answer 1

这个问题的经典2近似算法，运行时间为O(nd)，是选择一个任意点，然后返回到另一个点的最大距离。 直径不小于这个值，也不大于两倍这个值。

- David Eisenstat

---

@G.Samaras 下限是显而易见的。上限是一个带有三角不等式的行。 - David Eisenstat

我明白你的意思。不过，让我再等一会儿看看是否有其他答案出现。 :) 非常感谢。+1 - gsamaras

可选扩展：选择随机点x。选择距离x最远的点y。选择距离y最远的点z。然后可以使用y和z之间的距离来代替您的界限。 - Timothy Shields

@ TimothyShields，你能解释一下我如何证明这个限制吗？如果你觉得需要另一个答案，请随意发表，因为我希望我们不会在David的回答中打扰他太多。 :) - gsamaras

@G.Samaras 这基本上是相同的证明。令 D = d(p,q) 为直径。那么 d(y,z) ≤ D（因为 p,q 是 d(*,*) 的最大参数），且 D = d(p,q) ≤ d(p,y) + d(y,q) ≤ 2d(y,z)（三角不等式和 z 是 d(y,*) = d(*,y) 的最大参数）。 - David Eisenstat

Answer 2

我想添加一条评论，但是声望值不够...

我只想警告其他读者，“边界框”解决方案非常不准确。例如，以半径为一的欧几里得球为例，该集合的直径为二，但其边界框[-1，1] ^ d的直径为平方根d的两倍。对于d = 128，这已经是一个非常糟糕的近似。

对于一个粗略的估计，我会选择David Eisenstat的答案。

- Augusto T.

Answer 3

我将总结提出的Timothy Shields算法。

1. 随机选择一个点x。
2. 选择离x最远的点y。
3. 如果没有完成，让x=y，并转到步骤2

重复次数越多，结果将会更加准确... ??

编辑: 实际上这个算法并不是很好。想象一个有顶点ABCD的二维矩形。存在两个最大值：在AC和BD之间，它们被一个相当大的山谷分开。该算法将在其中一个最大值卡住50/50。如果AC稍微大于BD，你将无论迭代多少次都会得到错误的答案。其他正则多边形也存在同样的问题，在更高维度中问题更为严重。

- John Henckel

Answer 4

有一种基于精度的算法，对于任何维度都表现得非常好，它基于计算轴向边界框的维度。

其思想是可以找到轴向边界框长度函数的下限和上限，因为它的偏导数是有限的，并且取决于轴之间的角度。

在2D空间中两个轴之间局部极大导数的极限可以计算为：sin(a/2)*(1 + tan(a/2))。这意味着例如，在轴之间为90度时，边界为1.42（sqrt(2)）。

当a > 0时，这将缩减为a/2，因此上边界与角度成比例。

对于多维情况，公式略有不同，但仍然很容易计算。

因此，寻找局部极小值的搜索在对数时间内进行。

好消息是我们可以并行运行这样的局部极大值搜索。此外，我们可以根据迄今为止取得的最佳结果过滤出搜索区域以及搜索区域中低于搜索下限的点本身。

该算法的最坏情况是所有点都放置在球体的表面上。

这可以进一步改进：当我们检测到仅在少数点上操作的本地搜索时，我们会为该特定轴切换到暴力破解。它工作得很快，因为我们只需要那些受制于特定本地搜索的点，可以确定为由共享同一轴的特定角度的两个相反球形锥体所限制的点。

很难确定大O符号，因为它取决于所需精度和点的分布（当大多数点位于球面表面时效果不佳）。

我使用的算法在这里：

1. 将初始角度a = pi/2设置。
2. 为每个维度取一个轴。角度和轴形成初始“桶”。
3. 对于每个轴，通过将所有点投影到轴上并找到轴上坐标的最小值和最大值来计算该轴上的跨度。
4. 计算有趣直径的上下界。它基于公式：sin（a/2）*（1 + tan（a/2）），并乘以从当前轴投影长度计算出的不对称系数。
5. 对于下一步，在同一维度中同时落在下限以下的所有点都被删除。
6. 对于每个轴，如果在上限以上的点的数量少于某个合理数量（经过实验计算），则在问题点集上使用暴力（N ^ 2）进行计算，并调整下限，并在下一步中删除轴。
7. 对于下一步，删除所有其所有点均在下限以下的轴。
8. 如果精度满意（上限 - 下限）< epsilon，则将上限作为结果返回。
9. 对于所有幸存的轴，存在一个虚拟锥体（实际上是两个相反的锥体），它覆盖了包围立方体面的虚拟球体上的一些区域。如果我没记错，它的角度将是a * sqrt（2）。将新角度设置为a / sqrt（2）。创建一整个新轴桶（2 *维数），以便新锥体区域覆盖初始锥体区域。这对我来说是困难的，因为我对n> 3维情况的想象力不足。
10. 从步骤（3）继续。

你可以并行执行该过程，同步计算到目前为止从（5）到（7）的点的限制。

- George Polevoy