algorithm - 2 点間の最小距離を計算する最も高速なアルゴリズムは何ですか?

Question

100万個の頂点を持つ2つのポリゴン間の最小距離を見つけたい(頂点間の最小距離ではありません)。最初の形状の各頂点と他の形状のすべての頂点との間の最短距離の最小値を見つける必要があります。Hausdorff Distanceのようなものですが、最大ではなく最小が必要です。

Answer 1

おそらく、チェックアウトする必要があります ( PDF の警告! また、何らかの理由で、ページの順序が逆になっていることに注意してください)、Toussaint と Bhattacharya による " Optimal Algoriths for Computing the Minimum Distance Between Two Finite Planar Sets ":

この論文では、[ sic ] n 個のポイントの場合の 2 つの有限平面集合間の最小距離は、O( n log n ) の最悪の場合の実行時間で計算でき、これは一定の係数内で最適であることが示されています。さらに、セットが凸多角形を形成する場合、この複雑さは O( n ) に減らすことができます。

2 つのポリゴンが凸面ポリゴンと交差している場合は、おそらくチェックアウトする必要があります ( PDF の警告! 繰り返しますが、ページの順序が逆になっています) 。Toussaint による「 2 つの交差する凸面ポリゴン間の最小頂点距離を計算するための最適なアルゴリズム」:

P = { p 1 _, p 2 _, ..., p _m } と Q = { q ₁ , q ₂ ,..., q _n } を 2 つの交差する多角形とし、その頂点はデカルト座標によって順番に指定されます。Pの頂点p _iとQの頂点q _jの間の最小ユークリッド距離を計算するための最適な O( m + n ) アルゴリズムが提示されます。