マンハッタン距離が最小の2点を見つける方法

1. 序章

このチュートリアルでは、マンハッタン距離が最小の2Dポイントのペアを見つける方法を示します。

2. 最小マンハッタン距離

2次元の点があるとしましょう。 マンハッタン距離ごとに最も近い2つを見つけたい。垂直セグメントと水平セグメントのみを含む2点間の最短直線パスの長さを測定します。

したがって、マンハッタン距離を計算するための式は次のとおりです。

(1)

3. アルゴリズム

力ずくのアプローチに従い、ポイントのすべてのペアを反復処理して、各2つの間の距離を計算し、最も近いペアを返すことができます。ただし、そのアルゴリズムの時間計算量は2次式です。

代わりに、分割統治戦略を使用して、より効率的なアルゴリズムを設計できます。最も近いペアを見つけることは計算幾何学の基本的な問題であるため、それを解決するための高速な方法が必要です。

3.1. 分割統治アプローチ

線を引いて左右に分割してみましょう。

ここで、全体で最も近いペアは、の最も近いペア、の最も近いペア、または一方の点がにあり、もう一方の点がにある最も近いペアのいずれかです。

したがって、で最も近いペアを見つけるには、最初にその左半分と右半分で最も近いペアを決定する必要があります。これは、元の問題を2つの小さなサブ問題に分割するステップです。それがの最小距離であり、がの最小距離であるとしましょう。の場合、の最も近い2つのポイントは、分割線に沿った幅の広いストリップにある場合にのみ、より短い距離にあります。

したがって、組み合わせの手順は、ストリップの最小距離を見つけて、それをと比較することで構成されます。

これにより、recursiveアルゴリズムが得られます。基本ケースとして、3つのポイントを含むものを取り上げ、3つのペアすべてを検査して解決しますが、他の選択肢もあります。

3.2. 最悪の場合の実行時間分析

ポイントを使用した入力の最悪の実行時間とし、とに分割して検索するコストを示します。次に、次の再発があります。

(2)

-ワイドストリップにないすべてのポイントをスキャンして削除するには時間がかかるため、。最悪の場合、すべてのペアがストリップに含まれる可能性があるため、列挙型アプローチがステップを実行し、再発は次のようになります。

マスター定理を使用すると、が得られます。しかし、それは非効率的なブルートフォースアルゴリズムよりも優れているわけではなく、分割のコストも考慮していませんでした。アルゴリズムを高速化するために何かできることはありますか？幸いなことに、ストリップ内のポイントは、すばやく見つけることができる特別な構造になっています。確かに、アルゴリズムを実装して、再発（2）が解に評価されるようにした場合。

3.3. 垂直マンハッタンストリップは特別な構造を持っています

の最も近い2つのポイントがストリップ（）にあると仮定します。なぜなら、垂直方向に、それらが離れている以上のことはできないと確信できるからです。

とを含む長方形から、およびを含むことができる他のポイントはいくつありますか？ すべてのポイントが距離にあるため、から最大5つのポイントが長方形の左半分に存在できます。についても同じことが言えます。

したがって、ストリップ内のポイントを-座標で並べ替えると、とのインデックスは最大で9だけ異なります。したがって、ストリップ内の各ポイントについて、-sorted配列でそれに続く9つだけをチェックする必要があります。その結果、線形時間で見つけることができます。ただし、各再帰呼び出しでポイントを並べ替えると、が得られ、アルゴリズム全体を対数線形にするために線形にする必要があります。

3.4. 並べ替え

事前に並べ替えることでそれを実現します。 事前に-axisで並べ替えた場合、線形時間でポイントを-sortedと各呼び出しに分割できます。の-sortedコピーをとして示します。

ポイントの座標で分割するので、ソートされたコピーも保持する必要があります（と表記します）。次に、中央のコピーの中央のインデックスを使用して、時間内に左半分と右半分に分割できます。再帰呼び出しを行う前に、とに分割するのと同じように、とに分割する必要があります。マージソートのマージステップを逆にすることにより、線形時間でこれを行います。

最悪の場合、マージソートで事前ソートを行うことができます。を使用すると、アルゴリズムにも時間がかかるため、事前ソートによって全体の複雑さが損なわれることはありません。