algorithm - 点集合 P の任意の点までの最大距離が最小になるような点を見つける

Question

Pi = (Xi, Yi) である 2 次元空間 P の一連の点が与えられると、

Pi までの最大距離が最小になるような目標点 T を見つける必要があります。

T は P に存在する必要はなく、任意に定義できます

これに使用できるアルゴリズムはありますか?

score 8 · Accepted Answer

8

これは最小円問題です。

于 2012-05-24T15:03:50.083 に答える

score 1 · Accepted Answer

これはかなり良い説明であなたの問題の解決策になるかもしれないと思いますが、それは O(n^2) です

score 0 · Accepted Answer

私はそれを証明していませんが、解決策は次のとおりだと思います。

(最小(Xi) + 最大(Xi)) / 2, (最小(Yi) + 最大(Yi))/2)

3 に答える 3