他の点のセットとの距離の合計が最小である点を見つける

Question

私は、1セット（X）の点（それほど大きくないと言えば1〜20点）と2番目の（Y）私はYからいくつかのポイントを選択する必要があります。すべてポイントまでの距離は最小です。

私は、Xをポリゴンの頂点として扱い、このポリゴンの重心を見つけて、セントロイドに最も近いYからポイントを選択するという考えを思いつきました。しかし、重心がポリゴンの頂点までの距離の和を最小にするかどうかはわからないので、これが良い方法かどうかはわかりません。この問題を解決するアルゴリズムはありますか？

ポイントは地理座標で定義されます。

Answer 1

ポリゴンの重心は正しくないかもしれませんが、そのような点が存在します。論文で

： n-ellipses and the minimum distance problemは、ポイント（Xのあなたのセット、巣と呼ばれる）場合の合計のためのユニークなポイント（と呼ばれる中央）があり、その後

• を同一線上にされていないことを示しています距離の最小化が図られる。この点は、その点から焦点までの単位ベクトルの合計がゼロであるようなものです！

距離の和が一定であるために点の軌跡が中心に距離Dため

• N-楕円を含む（N-楕円と呼ばれる）に凸の曲線を完全にするためのn楕円を含んで

• 任意の他の距離D「のD」< D.

は、このようにあなたは、中心を見つけるために、山登りアルゴリズムのいくつかの種類を行うことができます。

もちろん、これらのn楕円は必ずしも円である必要はないので、中心に最も近い点を選ぶだけではうまくいかないかもしれませんが、近似値が良いかもしれません。

（上記の情報に基づいて）良好なパーティショニングスキームを把握するために、20ポイント（それらが修正されている場合）でいくつかの前処理を行うことができます。

希望に役立ちます。

Answer 2

あなたは距離の二乗和（距離のない総和）を最小にしたい場合は、その和を最小ポイントはX.

証明に点の平均である：

誘導体は、とき Nx = x0+x1+...発生し、ゼロであるので、 x = (x0+x1+...)/N

誘導体は、この点の周りに対称である、と関数が二次であるので、私は最も近いPOINかなり確信しているときの和が最小化された

sum(squares of distances) = (x-x0)^2 + (y-y0)^2 + (x-x1)^2 + (y-y1)^2 + ... 

d/dx sum(squares of distances) = 2(x-x0) + 2(x-x1) + ... = 2(Nx - x0 - x1 - ...) 

この平均点に対するYのtが最良です。

距離を最小限に抑えるのは難しいですが、私は同じアルゴリズムを使用していると思われます。テストするYのセットの余裕が増えればうまくいくでしょう。

Answer 3

距離の最小値を求めたいので、点集合Xを空間平均に減らすことができると思います。次に、KDTreeや何らかの種類の空間分割木を使用して、Xの空間平均に最も近いY内の点を見つけることができます。空間分割木を使用すると、すべての可能な点を調べるのに比べて作業の節約になります。

Answer 4

私はブルートフォースを示唆しています。 質問がどのように提起されるかは、X、Yがどこにあるのかわからない。 Xが30ポイント、Yが1000ポイントとします。 次に、Yの各点に対して30の距離を合計します。 全部で30000回の計算が完了しました。 これにより、最小値が保証されます。 Xのいくつかの「中心」を見つけて、最も近いYを選択するのはおおよその解決策にすぎません。

さらに興味深い質問は、Xだけでそのような点を見つけることです。 Yを無視する Xの3点のみについては、Fermat-Torichelliポイントが問題を解決します。