最も遠いポイントのペアを決定する
1. 概要
このチュートリアルでは、特定のポイントのセットから最も遠いポイントのペア間の距離を見つける問題について説明します。
まず、問題を定義し、それを説明するための例を示します。 次に、それを解決するための2つの異なるアプローチを提示し、それらの実装と時間計算量を処理します。
2. 問題の定義
平面上のデカルト座標に一連の点があるとします。 可能なすべてのポイントのペア間の最大距離を見つけるように求められました。
次の例を見てみましょう。
とポイントが与えられ、そして：
3つの可能なポイントのペアがあります。
- 距離付き。
- 距離付き。
- 距離付き。
ご覧のとおり、最大距離はポイントとの間であり、に等しくなります。
3. 素朴なアプローチ
3.1. 本旨
このアプローチの主なアイデアは、可能なすべてのポイントのペアを総当たり攻撃し、最大距離のペアを取得することです。
最初に、目的のペアの最初のポイントになる可能性のあるすべてのポイントを確認します。 次に、各ポイントの他のすべてのポイントで試してみます。 その後、各ペアについて、現在のペアのポイント間の距離でこれまでの最大距離を最大化しようとします。
最後に、答えはすべての可能なポイントのペア間の最大距離に等しくなります。
3.2. アルゴリズム
アルゴリズムの実装を見てみましょう。
最初に、可能なすべての点のペア間の最大距離を返す関数を宣言します。 関数には、指定されたポイントのセットを表す1つのパラメーターがあります。
次に、最大距離を格納するを宣言します。最初は、に等しくなります。 次に、可能なすべてのポイントのペアをブルートフォースします。 各ポイントについて、他のすべてのポイントを反復処理し、現在のペアのポイント間の距離を確認します。 距離が現在よりも大きい場合は、現在のペアのポイント間の距離に等しくなるように更新します。
最後に、はポイントの任意のペア間の可能な最大距離に等しくなります。
3.3. 複雑さ
このアルゴリズムの時間計算量はです。ここで、は指定されたポイントの数です。 この複雑さは、各ポイントについて、他のすべてのポイントを反復処理しているためです。
4. キャリパーを回転させるアプローチ
4.1. 本旨
このアプローチの背後にある主なアイデアは、ポイントの最も距離のペアは、指定されたポイントのセットの凸包の頂点からのものであり、取得できる最大距離はその直径に等しいということです。凸多角形。
このアプローチを2つのフェーズに分割します。
- 凸包：目的の点のペアが凸包の頂点に属するため、指定された点のセットの凸包を作成します。 その背後にある理由は、凸包の内側にある1対の点によって定義される線分を取得する場合、その線分の端を凸包の境界に接触するように延長できるためです。 したがって、より良い解決策が得られます。
- 凸多角形の直径：凸多角形の頂点から取得できる最も遠い点のペアは、その多角形の直径を定義する頂点のペアになります。
したがって、最大距離は、指定された点のセットから形成される凸包の直径の長さです。
4.2. 凸包
凸包アルゴリズムの構築の実装を見てみましょう。
最初に、指定された点のセットによって定義された凸包の頂点を返す関数があります。 関数には、指定されたポイントのセットを表す1つのパラメーターがあります。
最初に、凸包の最初の頂点となるを宣言します。これは極値であり、凸包の頂点からのものであることを保証できるため、x座標の最小値を持つ点と等しくなります。
次に、セットからを削除し、残りのポイントを勾配に従って並べ替えます。
ご覧のとおり、ポイントはx座標値が最小のポイントであるため、残りのポイントの傾きに応じた順序はになります。
第三に、凸包の頂点を格納するリストを宣言します。 凸包の頂点からのものであるため、にを追加します。 次に、ソートされたポイントを繰り返し処理します。
2つのベクトルを作成します。 最初の1つは、現在の凸包の最後の2つのポイント間のベクトルを表し、もう1つは、最後のポイントの前のポイントと既存のポイントの間にあります。 各点について、凸包に少なくとも2つの点がありますが、最後の点が凸包の頂点の1つであるかどうかを確認します。
これら2つのベクトルの外積がゼロ以下の場合、現在のポイントを追加して右折します。 したがって、最後のポイントは有効であり、ループから抜け出します。 それ以外の場合は、左に曲がります。これは、現在のポイントが最後のポイントよりも優れていることを意味します。 したがって、最後のポイントをからポップします。 最後に、現在の点を凸包に追加します。
ご覧のとおり、現在にはポイント、、、があります。 凸包に追加したい場合は、最後の2点で左折します。 したがって、から最後のポイントをポップします。
最後に、凸包の頂点が時計回りに並べ替えられます。
4.3. 凸多角形の直径
アルゴリズムの実装を見てみましょう。
最初は、前のアプローチと同じ機能があります。 最大距離は、凸包の直径の長さに等しくなります。 さらに、直径の長さは、すべての対蹠ペアの距離の中で最大値に等しくなります。 （ポリゴンの頂点のペアを思い出して、サポートの平行な接線上にある場合は対蹠ペアと呼びます）。
まず、与えられた点の凸包に等しくなります。 また、凸多角形のサイズに等しいを宣言します。 次に、凸多角形の最初の点と最後の点によって定義される線分への最も遠い点の位置を表すポインタを用意します。これは、最初の点との対蹠点になります。
その後、の面積が：の面積よりも小さい間、ポインターを動かし続けます。
次に、対蹠ペアがあります。次に、回転キャリパー法を使用してすべての対蹠ペアを取得します。最初のポインターを移動している間、セグメントから可能な限り離れるように移動し続けます。 現在の対蹠ペア間の距離が現在よりも大きい場合は、をその値と等しくなるように更新します。
最後に、はポイントの任意のペア間の可能な最大距離に等しくなります。
4.4. 複雑
このアルゴリズムの時間計算量はです。ここで、は指定されたポイントの数です。 この複雑さの背後にある理由は、凸包を構築する前にポイントをソートするため、凸包を構築することの複雑さです。
また、回転キャリパー手法の時間計算量は、2つのポインターのそれぞれがポリゴンの頂点を最大で1回通過するためです。 したがって、このアプローチの全体的な複雑さはです。
5. 結論
この記事では、特定のポイントのセットから最も遠いポイントのペア間の距離を見つける問題について説明しました。 問題を説明するための例を提供し、問題を解決するための2つの異なるアプローチを検討しました。ここで、2番目のアプローチの方が時間計算量が優れていました。
最後に、それらの実装をウォークスルーし、それぞれの背後にある考え方を説明しました。
