Fortune’s algorithm とは

Fortuneのアルゴリズムは、O(n log n)の時間とO(n)の空間を使って平面上の点の集合からボロノイ図を生成するスイープラインアルゴリズムです。これは1986年にSteven Fortuneによって「ヴォロノイダイアグラムのスイープラインアルゴリズム」と題して発行されました。