在d維空間中查找一組n個點的直徑

Question

我很有興趣在128維中找到兩個點集的直徑。第一個有10000點，第二個1000000.因此，我想要做一些比O（n2）的天真方法更好的做法。該算法將能夠處理任意數量的點和維度，但我目前對這兩個特定數據集非常感興趣。

我對提高精度速度非常感興趣，因此，根據this，我會通過計算每個座標的最小值和最大值來找到點集的（近似）邊界框，因此O（n * d ） 時間。然後，如果我找到這個盒子的直徑，問題就解決了。

在3d的情況下，我可以找到一邊的直徑，因爲我知道兩邊，然後，我可以將畢達哥拉斯定理應用於垂直於這邊的另一邊。然而，我不確定這一點，當然，我也看不出如何將它推廣到d維。

---

一個有趣的答案可以發現here，但它似乎是特定的3個維度，我想爲d維的方法。

有趣的論文：計算高維歐幾里得空間中一個點集的直徑。 Link。然而，在這個階段對我來說實現算法似乎太多了。

Answer 1

這個問題的經典2-近似算法，運行時間O（nd），是選擇一個任意點，然後返回到另一個點的最大距離。直徑不小於此值，不大於此值的兩倍。

Answer 2

有一種基於精度的算法，在任何維度上表現都很好，這是基於計算軸向邊界框的尺寸。

這個想法是可以找到軸邊界框長度函數的下邊界和上邊界，因爲它的偏導數是有限的，並且取決於軸之間的角度。

在2D空間中的兩個軸系之間的局部最大值衍生物的限制可以被計算爲：

SIN（A/2）*（1 +黃褐色（A/2）） 這意味着，例如，對於軸之間的90度，邊界爲1.42（sqrt（2））

當a => 0時，它減少到a/2，所以上邊界與角度成正比。

對於多維情況，公式稍有不同，但仍然很容易計算。

因此，局部極小值的搜索會在對數時間內卷積。

好消息是我們可以同時運行這樣的本地最大值搜索。 此外，我們可以根據迄今爲止取得的最佳結果以及在最差的區域內搜索下限的點本身來篩選出搜索區域。

算法的最壞情況是所有的點都放在球體的表面上。

這可以進一步改進：當我們檢測到一個只在少數點上操作的局部搜索時，我們將交換爲這個特定軸的蠻力。它的工作速度很快，因爲我們只需要受到特定局部搜索的點，這些點可以確定爲實際上由共享相同軸的特定角度的兩個相反球面錐體限定的點。

很難弄清大O符號，因爲它取決於期望的精度和點的分佈（當大多數點位於球體表面時都不好）。

我使用該算法是在這裏：

1. 設置初始角度= pi/2之間。
2. 每個維度取一個座標軸。角度和軸形成初始「桶」
3. 對於每個軸，通過將所有點投影到該軸上並計算軸上的座標的最小值和最大值來計算該軸上的跨度。
4. 計算有趣的直徑的上限和下限。它基於以下公式：sin（a/2）*（1 + tan（a/2））並乘以assimetry cooficient，根據當前軸投影的長度計算得出。
5. 對於下一步，同時殺死每個維度下邊界下的所有點。
6. 對於每個exis，如果高於上限的點數小於某個合理的數值（通過實驗計算），那麼使用對該點集合的bruteforce（N^2）進行計算，並調整下限，並在下一步中關閉該軸。
7. 對於下一步，殺死所有的軸，它們的所有點都在下界下。
8. 如果精度令人滿意（上限 - 下限）< epsilon，則返回上限作爲結果。
9. 對於所有存活的軸線，該軸上有一個虛擬錐體（實際上是兩個相對的錐體），它覆蓋包圍立方體的一個面的虛擬球體上的一些區域。如果我沒有弄錯，它的角度將是* sqrt（2）。將新角度設置爲a/sqrt（2）。創建一個新的軸的桶（2 *維數），所以新的錐體區域將覆蓋最初的錐體區域。這對我來說很難，因爲對於三維情況我沒有足夠的想象力。
10. 從步驟（3）繼續。

您可以將過程同步，同步從（5）到（7）中的點計算出的極限值。

Answer 3

我想添加評論，但沒有足夠的信譽爲保證，...

我只是想提醒其他讀者的「邊框」的解決方案是非常不準確的。以例如半徑1的歐幾里德球爲例。該集具有直徑2，但其邊界框是[-1,1]^d，其直徑是d的平方根的兩倍。對於d = 128，這已經是一個非常糟糕的近似值。

對於粗略估計，我會留在大衛艾森斯塔特的答案。