具有距離函數的集合的最大直徑

Question

我有一組元素與滿足三角不等式的元素之間的距離函數。

我想找到由最大距離分隔的元素對。

有沒有比嘗試所有配對更好的解決方案？

Answer 1

如果您測量從點a到點b，c和d的距離，並且您發現| ab | + | ac | < | ad |，那麼你知道| bc |比| ad |短，並且不需要測量| bc |。因此，不需要檢查所有對以找出最長的距離。

一種可能的算法是：
通過測量從點a到所有其他點的距離，找到距離a最遠的點n，然後給出所有對b，x，其中| ab | + |斧頭| < | an |距離| ab | + | ax | （因爲那是他們最大可能的距離）。
對b點做同樣的測量，只測量尚未設定的距離。檢查你是否找到了一個新的最大值，然後再給出所有對c，x的| bc | + | bx | < MAX距離| bc | + | bx |。
繼續做這點C，d，...

在最好的情況下，你會發現剛剛N-1測量後一組的N個點的距離最長的（如果|斧頭|兩倍只要與a）有任何其他距離。在最糟糕的情況下，您需要測量每一對（如果最短距離超過最長距離的一半，或者運行順序不正確）。

---

如果你想距離測量的數量減少到最低限度，併爲每一個未知的距離X，Y你檢查每一個先前存儲的值| AX | + | AY |，| BX | + |通過|，| cx | + | cy | ...看它是否小於當前最大值，因此可用作| xy |的值，測量次數大大減少。

在正方形2D空間中的1000個隨機點上運行此算法（通常需要499,500次測量）返回2000到10000次測量的最大距離（或總量的0.4％到2％之間，平均值爲1％）。

這並不一定意味着該算法在實踐中比測量每個距離快得多;這取決於測量的成本與迴路的組合以及避免測量所需的附加和比較的成本。

---

正如@mcdowella指出的那樣，這個方法變得的空間增大的維數效率較低。點數也有很大的影響。下表顯示了必須進行的測量次數與總對數的關係。這些是來自「方形」空間中隨機分佈點的測試的平均值（即，所有維度中的座標都在相同範圍內）。正如你所看到的，這種方法對於2D或3D空間中有許多點的幾何問題最有意義。但是，如果您的數據在某些方面存在高度偏倚，則結果可能會有所不同。

 
     10 points (45 pairs)  100 points (4950 pairs) 1000 points (499500 pairs) 
dim measurem. % of total measurem. % of total measurem. % of total 

1  16.6674  37.04   221.17  4.47  4877.97  0.98 
2  22.4645  49.92   346.77  7.01  5346.78  1.07 
3  27.5892  61.31   525.73  10.62  7437.16  1.49 
4  31.9398  70.98   731.83  14.78  12780.02  2.56 
5  35.3313  78.51   989.27  19.99  19457.84  3.90 
6  38.1420  84.76  1260.89  25.47  26360.16  5.28 
7  40.2296  89.40  1565.80  31.63  33221.32  6.65 
8  41.6864  92.64  1859.08  37.56  44073.42  8.82 
9  42.7149  94.92  2168.03  43.80  56374.36  11.29 
10  43.4463  96.55  2490.69  50.32  73053.06  14.63 
20  44.9789  99.95  4617.41  93.28  289978.20  58.05 
30  44.9996  99.999  4936.68  99.73  460056.04  92.10 
40        4949.79  99.99  496893.10  99.48 
50        4949.99  99.9999 499285.80  99.96 
60              499499.60  99.9999 

正如預期的那樣，該測試的結果變得可預測在更高的層面，與異常之間只有百分之幾，而在2D需要比其他人的30倍以上測量一些測試用例。