フォーチュンのアルゴリズム

フォーチュンのアルゴリズムは、O ( nlogn ) の 時間とO( n )の空間を使用して、平面上の点の集合からボロノイ図を生成するスイープラインアルゴリズムです。 ^{[1] [2]}これは、1986年にスティーブン・フォーチュンによって論文「ボロノイ図のスイープラインアルゴリズム」で最初に発表されました。^[3]

このアルゴリズムはスイープ ラインとビーチ ラインの両方を維持し、アルゴリズムが進むにつれて両方とも平面内を移動します。スイープ ラインは直線で、慣例により垂直で平面を左から右に移動するものとします。アルゴリズムの実行中はいつでも、スイープ ラインの左側の入力ポイントはボロノイ図に組み込まれますが、スイープ ラインの右側のポイントはまだ考慮されません。ビーチ ラインは直線ではなく、スイープ ラインの左側にある複雑な区分曲線で、放物線の断片で構成されています。ビーチ ラインは、スイープ ラインの右側に他のポイントが何であるかに関係なく、ボロノイ図を把握できる平面の部分を、平面の残りの部分から分割します。スイープ ラインの左側の各ポイントについて、そのポイントとスイープ ラインから等距離にあるポイントの放物線を定義できます。ビーチ ラインは、これらの放物線の結合の境界です。スイープ ラインが進むにつれて、2 つの放物線が交差するビーチ ラインの頂点が、ボロノイ図の端を描きます。ビーチ ラインは、各放物線の底辺を、スイープ ラインで最初にスイープされた点とスイープ ラインの新しい位置のちょうど中間に保ちながら進みます。数学的には、これは、スイープ ラインを準線として使用し、入力点を焦点として使用して各放物線が形成されることを意味します。

アルゴリズムは、データ構造として、ビーチ ラインの組み合わせ構造を記述するバイナリ検索ツリーと、ビーチ ライン構造を変更する可能性のある将来のイベントをリストする優先キューを維持します。これらのイベントには、ビーチ ラインへの別の放物線の追加 (スイープ ラインが別の入力ポイントを横切るとき) や、ビーチ ラインからの曲線の削除 (スイープ ラインが、ビーチ ラインの連続するセグメントを形成する放物線のある 3 つの入力ポイントを通る円に接するとき) が含まれます。このような各イベントは、イベントが発生したポイントでのスイープ ラインのx座標によって優先順位が付けられます。アルゴリズム自体は、優先キューから次のイベントを繰り返し削除し、イベントがビーチ ラインに引き起こす変更を見つけ、データ構造を更新することから構成されます。

処理するイベントは O( n )個あり（それぞれがボロノイ図のいくつかの特徴に関連付けられている）、イベントの処理時間は O(logn )個（それぞれが定数個のバイナリ検索ツリーと優先キュー操作で構成されている）であるため、合計時間は O( nlogn )になります。

アルゴリズムの擬似コード記述。 ^[4]

 を変換、
  をzと最も近いサイト
間のユークリッド距離とする。 T を「ビーチ ライン」と
する。 をサイトpによってカバーされる領域とする。
をサイトpとq間の境界光線とする。
をこのアルゴリズムを適用するサイトのセットとする。 を
Sから抽出した、最小のy座標を持つサイトとし、 x座標
で順序付けする。 DeleteMin( X ) をXの最も低く左端のサイトを削除する操作とする(同じでない限り y で並べ替え、同じ場合は x で並べ替える)。 
 V をこのアルゴリズムによって構築される
Sのボロノイ マップとする。初期の垂直境界光線を作成する${\displaystyle \scriptstyle *(z)}$${\displaystyle \scriptstyle *(z)=(z_{x},z_{y}+d(z))}$ ${\displaystyle \scriptstyle d(z)}$  ${\displaystyle \scriptstyle R_{p}}$ ${\displaystyle \scriptstyle C_{pq}}$ ${\displaystyle \scriptstyle S}$ ${\displaystyle \scriptstyle p_{1},p_{2},...,p_{m}}$ ${\displaystyle Q\gets {p_{1},p_{2},\dots ,p_{m},S}}$
${\displaystyle \scriptstyle C_{p_{1},p_{2}}^{0},C_{p_{2},p_{3}}^{0},\dots ,C_{p_{m-1},p_{m}}^{0}}$
${\displaystyle T\gets *(R_{p_{1}}),C_{p_{1},p_{2}}^{0},*(R_{p_{2}}),C_{p_{2},p_{3}}^{0},\dots ,*(R_{p_{m-1}}),C_{p_{m-1},p_{m}}^{0},*(R_{p_{m}})}$

IsEmpty( Q )ではないときにp ← DeleteMin( Q )
    を実行します。p
    のpが次のサイトである場合:  
    ${\displaystyle \scriptstyle *(V)}$T内にp を含む
        領域が存在するかどうかを調べる。${\displaystyle \scriptstyle *(R_{q})}$左側
          を で囲み、右側を で
        囲みます。底pを持つ新しい境界光線とを作成します。T内でで
        置き換えます。Qから と の間の任意の交差点を削除します。Qにとの間の任意の交差点を挿入します。Qにとの間の任意の交差点を挿入します。pは のボロノイ頂点です。
        左側と右側で
        pを の交差点とします。T内での左隣と を
        の右隣とします。の場合、
            新しい境界光線を作成します。そうでない場合、p がqとsのいずれか大きい方の右側にある場合は を作成します。
            そうでない場合は を作成します。endif Tで新しく作成された で
        置き換えます。Qからと の間の任意の交差点を削除します。Q からとの間の任意の交差点を削除します。Qにとの間の任意の交差点を挿入します。Qにとの間の任意の交差点を挿入します。pをの頂点、の底として
        記録します。
        境界線分とを出力します。endcase endwhile${\displaystyle \scriptstyle C_{rq}}$${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle C_{pq}^{-}}$${\displaystyle \scriptstyle C_{pq}^{+}}$${\displaystyle \scriptstyle *(R_{q})}$${\displaystyle \scriptstyle *(R_{q}),C_{pq}^{-},*(R_{p}),C_{pq}^{+},*(R_{q})}$
         ${\displaystyle \scriptstyle C_{rq}}$${\displaystyle \scriptstyle C_{qs}}$
         ${\displaystyle \scriptstyle C_{rq}}$${\displaystyle \scriptstyle C_{pq}^{-}}$
         ${\displaystyle \scriptstyle C_{pq}^{+}}$${\displaystyle \scriptstyle C_{qs}}$
    ${\displaystyle \scriptstyle *(V)}$ ${\displaystyle \scriptstyle C_{qr}}$${\displaystyle \scriptstyle C_{rs}}$ ${\displaystyle \scriptstyle C_{uq}}$${\displaystyle \scriptstyle C_{qr}}$ ${\displaystyle \scriptstyle C_{sv}}$${\displaystyle \scriptstyle C_{rs}}$
         ${\displaystyle \scriptstyle q_{y}=s_{y}}$${\displaystyle \scriptstyle C_{qs}^{0}}$ 
          ${\displaystyle \scriptstyle C_{qs}^{+}}$ 
        
             ${\displaystyle \scriptstyle C_{qs}^{-}}$
        ${\displaystyle \scriptstyle C_{qr},*(R_{r}),C_{rs}}$${\displaystyle \scriptstyle C_{qs}}$
         ${\displaystyle \scriptstyle C_{uq}}$${\displaystyle \scriptstyle C_{qr}}$
         ${\displaystyle \scriptstyle C_{rs}}$${\displaystyle \scriptstyle C_{sv}}$
         ${\displaystyle \scriptstyle C_{uq}}$${\displaystyle \scriptstyle C_{qs}}$
         ${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle C_{sv}}$${\displaystyle \scriptstyle C_{qr}}$${\displaystyle \scriptstyle C_{rs}}$${\displaystyle \scriptstyle C_{qs}}$${\displaystyle \scriptstyle C_{qr}}$${\displaystyle \scriptstyle C_{rs}}$
    

T
の残りの境界光線を出力する

^{フォーチュンが文献[1]}で述べているように、スイープラインアルゴリズムの修正版を使用して、各サイトまでの距離がサイトの重みによって相殺される加重ボロノイ図を作成できます。これは、サイトの重みに等しい半径を持つサイトを中心とするディスクセットのボロノイ図と同等に見ることができます。このアルゴリズムは、文献^[1]によると、nをサイトの数とすると、時間計算量があることがわかります。${\displaystyle O(n\log(n))}$

重み付けされたサイトは、ボロノイ図を使用してツリーマップを作成するときに、ボロノイ セルの領域を制御するために使用できます。加法的に重み付けされたボロノイ図では、サイト間の二等分線は一般に双曲線ですが、重み付けされていないボロノイ図やディスクのべき乗図では二等分線は直線になります。

• Steven Fortune の C 実装
• C++ で実装された Fortune の Voronoi アルゴリズム
• JavaScript で実装されたフォーチュンのアルゴリズム
• フォーチュンのアルゴリズムの視覚化