最遠優先走査

計算幾何学では、コンパクト距離空間の最遠優先走査は、空間内の点のシーケンスであり、最初の点は任意に選択され、後続の各点は、以前に選択された点の集合から可能な限り遠い点です。同じ概念は、選択された点をその集合に属するように制限するか、または同等にこれらの点によって生成される有限距離空間を考慮することによって、有限の幾何学的点の集合にも適用できます。^{[ 1 ]}有限距離空間または有限の幾何学的点の集合の場合、結果として得られるシーケンスは、貪欲順列としても知られる点の順列を形成します。^{[ 2 ]}

最遠点優先探索の各接頭辞は、広く離れていて残りのすべての点に近い点の集合を提供します。より正確には、同じ数の点の他の集合は、その2倍より広く離れてはならず、また、同じ数の点の他の集合は、残りの最も遠い点からの距離が半分未満になることもありません。これらの特性もあって、最遠点探索は、巡回セールスマン問題の近似やメトリックk中心問題など、多くの応用があります。これらは多項式時間で構築することも、（低次元ユークリッド空間の場合）ほぼ線形時間で近似することもできます。

最遠優先走査とは、コンパクト距離空間における点の列であり、各点は最大で 1 回しか出現しない。空間が有限の場合、各点はちょうど 1 回出現し、走査は空間内のすべての点の順列となる。列の最初の点は、空間内の任意の点であってもよい。最初の点以降の各点pは、列内のpより前の点の集合までの最大距離を持つ必要がある。ここで、点から集合までの距離は、集合内の点へのペアワイズ距離の最小値として定義される。与えられた空間には、列の最初の点の選択 (空間内の任意の点であってもよい) と、後続の選択における最大距離の同点の両方に応じて、多くの異なる最遠優先走査が存在する可能性がある。^{[ 2 ]}

最遠点探索は、以下の特性によって特徴付けられる。k という数を固定し、任意の距離空間の最遠点優先探索の最初のk個の点によって形成される接頭辞を考える。接頭辞の最後の点と接頭辞内の他の点との間の距離をrとする。この部分集合は、次の 2 つの特性を持つ。

• 選択された点のすべてのペアは互いに少なくともrの距離にあり、
• 距離空間のすべての点は、部分集合から最大でrの距離にある。

逆に、 kのすべての選択に対してこれらの特性を持つ任意のシーケンスは、最遠優先走査でなければなりません。これらはデローン集合の 2 つの定義特性であるため、最遠優先走査の各接頭辞はデローン集合を形成します。^{[ 3 ]}

Rosenkrantz、Stearns 、 Lewis（1977）は、最遠優先探索を用いて、巡回セールスマン問題の最遠挿入ヒューリスティックを定義した。このヒューリスティックは、最遠優先探索によって与えられた順序で、点のサブセット上にツアーを構築し、一度に1点ずつツアーに追加することで、巡回セールスマン問題の近似解を見つける。各点をツアーに追加するには、前のツアーの1つのエッジを切断し、追加された点を通る2つのエッジに置き換える。これは可能な限りコストの低い方法で行われる。Rosenkrantzらはこの方法の対数近似比しか証明していないが、実際には、より優れた近似比が証明可能な他の挿入方法よりも優れた結果を示すことが多いことを示している。^{[ 4 ]}

その後、同じ点列は、Gonzalez (1985)によって広く知られるようになりました。彼は、クラスタリングにおける 2 つの問題に対する貪欲近似アルゴリズムの一部としてこれを使用し、その目的は点の集合をk 個のクラスターに分割することです。Gonzalez がこのように解決した 2 つの問題のうちの 1 つは、クラスターの最大直径を最小化することを目指し、もう 1 つはメトリックk中心問題として知られており、クラスターの中心点から同じクラスター内で最も遠い点までの距離である最大半径を最小化することを目指します。たとえば、k中心問題は、市内のすべての住所に消防車が迅速に到達できるように、市内の消防署の配置をモデル化するために使用できます。どちらのクラスタリング問題でも、Gonzalez は、最も遠い点を優先して最初のk点を選択することによってk個のクラスター中心のセットを選択し、次に各入力点を最も近いクラスター中心に割り当てることによってクラスターを作成します。選択されたk個の中心の集合から、走査における位置k + 1 の次の点までの距離をrとすると、このクラスタリングでは、すべての点がその中心から距離r以内にあり、すべてのクラスターの直径は最大で2 rになります。しかし、 k個の中心のサブセットと次の点はすべて互いに少なくともr の距離にあり、任意のkクラスタリングでは、これらの点のうち 2 つが単一のクラスターにまとめられ、そのうちの 1 つは中心から少なくともr /2の距離にあり、直径は少なくともrになります。したがって、ゴンザレスのヒューリスティックは、両方のクラスタリング問題に対して 2の近似比を与えます。^{[ 3 ]}   

ゴンザレスのヒューリスティックは、メートルk中心問題に対してDyerとFrieze (1985)によって独立に再発見され、重み付きk中心問題に一般的に適用されました。^{[ 5 ]}同時期のk中心問題に関する別の論文、 HochbaumとShmoys (1985)は、同じ近似比 2 を達成していますが、^{[ 6 ]}その手法は異なります。^{[ 5 ]}それにもかかわらず、ゴンザレスのヒューリスティックと「最遠優先走査」という名前は、しばしば Hochbaum と Shmoys に誤って帰属されます。^{[ 7 ]}最小最大直径クラスタリング問題とメートルk中心問題の両方について、これらの近似は最適です。2 未満の任意の定数近似比を持つ多項式時間ヒューリスティックの存在は、P = NP を意味します。^{[ 3 ] [ 6 ]}

クラスタリングだけでなく、最遠優先探索は、施設配置問題の別のタイプである最大最小施設分散問題にも使用できます。この問題の目的は、k 個の異なる施設の位置を、互いにできるだけ離れるように選択することです。より正確には、この問題の目的は、与えられた距離空間または与えられた候補点の集合からk個の点を選択し、選択された点間の最小ペアワイズ距離を最大化することです。これもまた、最遠優先探索の最初のk個の点を選択することで近似できます。rがk番目の点からそれまでのすべての点までの距離を表す場合、距離空間または候補集合のすべての点は、最初のk − 1個の点からr以内の距離にあります。鳩の巣原理によ​​り、最適解 (それが何であれ) の 2 つの点は、選択された最初のk − 1個の点のうち同じ点からr以内の距離にあり、かつ (三角不等式により)互いに2 r以内の距離にある必要があります。したがって、最遠優先探索によって得られるヒューリスティック解は、最適解の2倍以内の精度である。^{[ 8 ] [ 9 ] [ 10 ]}    

最遠優先走査のその他の応用例としては、色量子化（画像内の色をより小さな代表色のセットにクラスタリングする）^{[ 11 ]} 、画像のプログレッシブスキャン（画像のピクセルを表示する順序を選択し、順序の接頭辞が画像全体の低解像度バージョンを生成するようにし、画像を上から下へ埋めるのではなく）^{[ 12 ]} 、モーションプランニングのための確率的ロードマップ法 における点選択^{[ 13 ]}、点群の単純化^{[ 14 ]}、ハーフトーン画像のマスク生成^{[ 15 ] [ 16 ]}、階層的クラスタリング^{[ 1 ]} 、類似した表面のポリゴンメッシュ間の類似性の検索^{[ 17} ]、水中ロボット探査のための多様で価値の高い観測対象の選択[ 18 ^] 、センサーネットワークの故障検出^{[ 19 ]}、系統的多様性のモデリング^{[ 20 ]}、異種車両群の車両を顧客の配送要求にマッチングする^{[ 18 ]などがあります。 21 ]}地球表面上の測地観測所の均一な分布^{[ 22 ]}、または他のタイプのセンサーネットワーク^{[ 23 ]} 、瞬時放射輝度コンピュータグラフィックスレンダリング方式での仮想点光源の生成^{[ 24 ]}、および幾何学的範囲検索データ構造^{[ 25 ]}。

• ロイドのアルゴリズムは、幾何学的空間に等間隔の点を生成する別の方法です。