このセクションでは、分割統治法を使用して最も近い点のペアを見つけるための効率的なアルゴリズムを紹介します。一連の点が与えられた場合、最近接ペア問題は、互いに最も近い 2 つの点を見つけることです。以下の図に示すように、最近接ペア アニメーションでは最も近い 2 点を結ぶ線が描画されます。

ケーススタディ: 最も近いペアの検索では、最も近い点のペアを見つけるための総当たりアルゴリズムを紹介しました。アルゴリズムは、すべての点のペア間の距離を計算し、最小距離を持つ点を見つけます。明らかに、アルゴリズムには O(n^2) 時間がかかります。より効率的なアルゴリズムを設計できますか?

この問題を解決するには、分割統治と呼ばれるアプローチを使用します。このアプローチでは、問題をサブ問題に分割し、サブ問題を解決し、サブ問題の解を組み合わせて問題全体の解を取得します。動的プログラミングのアプローチとは異なり、分割統治アプローチの部分問題は重複しません。部分問題は元の問題に似ていますが、サイズが小さいため、再帰を適用して問題を解決できます。実際、再帰的問題に対するすべての解決策は分割統治アプローチに従っています。

以下の手順では、分割統治アプローチを使用して最近接ペア問題を解決する方法を説明します。

• ステップ 1: 点を x 座標の昇順に並べ替えます。同じ X 座標を持つ点については、Y 座標に基づいて並べ替えます。これにより、ソートされたポイントのリスト S が生成されます。
• ステップ 2: ソートされたリストの中点を使用して、S を同じサイズの 2 つのサブセット S1 と S2 に分割します。中間点を S1 に置きます。 S1 と S2 で最も近いペアを再帰的に見つけます。 d1 と d2 が、それぞれ 2 つのサブセット内の最も近いペアの距離を表すものとします。
• ステップ 3: S1 の点と S2 の点の間で最も近いペアを見つけ、それらの距離を d3 として示します。最も近いペアは、距離が min(d1, d2, d3).
のペアです。

選択ソートには O(n^2) 時間がかかります。ステップ 1 は O(n log n) 時間で実行できます。ステップ 3 は O(n) 時間で実行できます。 d = min(d1, d2) とします。最も近いペアの距離が d より大きくならないことはすでにわかっています。 S1 の点と S2 の点が S で最も近いペアを形成するには、次の図に示すように、左側の点が stripL 内にあり、右側の点が stripR 内にある必要があります ( a).

stripL 内の点 p については、以下の (b) に示すように、d X 2d 長方形内の右側の点のみを考慮する必要があります。長方形の外側の任意の右点は、p と最も近いペアを形成できません。 S2 の最近接ペアの距離は d 以上であるため、最大で 6 つ存在する可能性があります 長方形内の点。したがって、
stripL の各点について、stripR 内の最大 6 つの点を考慮する必要があります。

stripL の各点 p について、stripR の対応する d X 2d 長方形領域内の点をどのように見つけますか? stripL および stripR 内の点が y 座標の昇順に並べ替えられている場合、これを効率的に行うことができます。 pointsOrderedOnY を、y 座標の昇順に並べ替えた点のリストとします。 pointsOrderedOnYはアルゴリズムで事前に取得できます。 stripL と stripR は、以下のコードに示すように、ステップ 3 の pointsOrderedOnY から取得できます。

if (p が S1 にあり、mid.x – p.x pをstripLに追加;
else if (p が S2 にあり、p.x - Mid.x pをstripR;
に追加

stripL および stripR の点を、次のように {p0, p1, ... , pk} および {q0, q1, ... , qt} とします。上図(c)。 stripL 内の点と stripR 内の点の間で最も近いペアは、以下のコードで説明されているアルゴリズムを使用して見つけることができます。