ボロノイ図

ボロノイ図とは

ボロノイ図は、ある距離空間において、複数の点が与えられた際に、空間内の各点がどの点に最も近いかによって領域を分割した図です。この「最も近い点」のことを母点またはサイトと呼びます。

特に、二次元ユークリッド平面におけるボロノイ図では、各領域の境界線は母点間の二等分線の一部となります。母点の配置によって分割パターンが決まるため、規則性を持たせることで美しい図形を作成することも可能です。

定義

距離空間 (X, d) 内の有限集合 P が与えられたとき、各点 p ∈ P を母点とします。このとき、点 x ∈ X が p のボロノイ領域 V(p) に含まれるとは、P 内の任意の点 q に対して、x と p の距離が x と q の距離以下であることを意味します。

math
V(p) = {x ∈ X | ∀q ∈ P [d(x, p) ≤ d(x, q)]}


ボロノイ図は、全ての母点に対するボロノイ領域を集めた集合です。ボロノイ領域の境界はボロノイ境界、ボロノイ境界の交点はボロノイ点と呼ばれます。

特徴

ボロノイ図およびボロノイ領域は、以下の重要な特徴を持ちます。

凸性: ボロノイ領域は常に凸領域となります。
等距離性: ボロノイ点は、その点を共有するボロノイ境界の母点から等距離に位置します。二次元ユークリッド平面の場合、ボロノイ点は母点を中心とする円の交点となります。

応用

ボロノイ図は、様々な分野で応用されています。

最近点探索: ある点に最も近い母点を効率的に探索するために利用されます。複雑な問題の部分問題として現れることも多く、ボロノイ図に基づいたデータ構造を用いることで高速な探索が可能です。
ロボット動作計画: 障害物を母点としたボロノイ境界上を経路とすることで、障害物を回避しながら目的地へ到達する経路を計画できます。この手法はレトラクション・アプローチと呼ばれます。
ドロネー三角形分割: ボロノイ図からドロネー三角形分割を生成できます。これは、ボロノイ領域が辺を共有する母点同士を線分で結ぶことで得られる三角形分割であり、理論・応用の両面で重要な性質を持ちます。
補間: 有限個の点における関数値から、他の点の関数値を推定する際に利用できます。推定したい点 x のボロノイ領域における、既知点のボロノイ領域の割合で重み付け平均を取ることで、関数値を補間します。

歴史

ボロノイ図の概念は、17世紀のデカルトにまで遡ることができます。ディリクレは19世紀に二次形式の研究でボロノイ図を使用し、ディリクレ空間分割という別名もあります。ボロノイ図の名は、一般の n 次元の場合を定義したロシア人数学者ゲオルギ・フェドセビッチ・ボロノイに由来します。

地球物理学や気象学では、ティーセン多角形としても知られています。また、凝縮系物理学ではウィグナー=サイツ単位セル、逆格子空間ではブリルアンゾーンと呼ばれています。

関連項目

ドロネー図
最近傍探索

もう一度検索