生長的曲線圖上的集合（X，Y）點

Question

問題：

給定一組在一個平面上的2D點的，找到一組邊Ë任意兩點之間的兩個平均行程時間最小化的和的大小E：即，通過將成本r與每個單位的行程時間和成本中的每個邊緣的成本相關聯。

我確定有一套處理這個問題的算法，但我似乎無法找到正確的搜索詞。我已經考慮從一個完整的圖形和修剪開始，但我想不出一種有效的方法來計算去除邊緣造成的損害。有什麼建議麼？大概（'夠好'）的解決方案歡迎。

讓我知道我的問題的陳述是否可以改進或澄清。

Answer 1

關於spanners的文獻中有一些工作與您所描述的有關（主要區別在於扳手控制最大拉伸，而您關心的是平均值）。 Chew的構造（「有一個和完整圖形幾乎一樣好的平面圖形」，SoCG'86）爲你的問題提供了一個O（1） - 近似，因爲三角形的邊數不到生成樹的三倍（因爲圖必須連接），並將每個歐幾里得距離調整至最大sqrt（10）（因此sqrt（10）乘以最優平均值）。