フォーチューンアルゴリズムによるボロノイ図の生成：O(n log n)の頭痛
2025-02-08
この記事では、O(n log n)の時間計算量でフォーチューンアルゴリズムを用いてボロノイ図を生成する複雑さを深く掘り下げています。著者は、実装が予想以上に困難であったことを認め、毎秒大量の大きな図形を処理する必要がない限り、より単純なO(n²)の方法やライブラリを使用することを推奨しています。この記事では、ボロノイ図、フォーチューンアルゴリズムの原理（スウィープライン、ビーチライン、イベントキュー、放物線など）、アルゴリズムのデータ構造とイベント処理（サイトイベント、サークルイベント、不完全なエッジ、ハーフエッジなど）を詳細に説明しています。複雑さにもかかわらず、このアルゴリズムは視覚的に素晴らしいボロノイ図を生成します。