ボロノイ図とは？
ぼろのいず
ボロノイ図とは、平面上の複数の点（母点）に対し、各点に最も近い領域を分割してできる図形のことです。
ボロノイ図（Voronoi diagram）とは、平面（あるいは高次元空間）上に複数の点（母点・シード）を配置したとき、「どの母点に最も近いか」によって空間を分割した図です。ロシアの数学者ゲオルギー・ボロノイにちなんで命名されました（デローネ分割とも深く関連します）。
各母点に対応する領域を「ボロノイ領域（ボロノイセル）」といい、隣接するセルの境界線は2つの母点から等距離にある点の集合、すなわち垂直二等分線によって構成されます。n 個の母点があれば、n 個のセルに空間が分割されます。
ボロノイ図は非常に幅広い分野で活用されています。
- 地理情報：最寄りの病院・コンビニ・施設の担当エリア分割
- 都市計画・物流：配送センターのカバー範囲設計
- 生物学：細胞の成長領域や動物の縄張りのモデル化
- コンピュータグラフィックス：テクスチャ生成やメッシュ作成
- 材料科学：金属の結晶粒界のシミュレーション
ボロノイ図の双対グラフはデローネ三角形分割と呼ばれ、こちらも計算幾何学で重要です。アルゴリズム的には、n 点に対して O(n log n) の時間計算量で構築できる効率的な手法が知られています。
使い方・例文
スマートフォンのマップアプリで「最寄りのコンビニ」の担当エリアを視覚化すると、ボロノイ図に似た形になります。ゲームのマップ生成やデータクラスタリングの可視化でも頻繁に使われます。
この用語をシェア
最終更新: