PROFILPELAJAR.COM

ボロノイ図（ボロノイず、英: Voronoi diagram）は、ある距離空間上の任意の位置に配置された複数個の母点（英: site、サイト）に対して、同一距離空間上の他の点がどの母点に近いかによって領域分けされた図のことである。特に二次元ユークリッド平面の場合、領域の境界線は、各々の母点の二等分線の一部になる。母点の位置のみによって分割パターンが決定されるため、母点に規則性を持たせれば美しい図形を生み出すことが可能。

定義

距離空間 $(X, d)$ 内の有限な部分集合 $P \subset X$ が与えられたとき、各点 $p \in P$ を母点またはサイトと呼び、これに対して、 $X$ の中で「 $P$ の点の中で $p$ が最も近い」点の集合

V(p)=\{x\in X\mid \forall q\in P\;[d(x,p)\leq d(x,q)]\}

を $p$ の(ボロノイ)領域と呼び、 $P$ の全ての点の領域を集めた集合（の誘導するセル複体）をボロノイ図と呼ぶ^[1]。

ボロノイ領域の境界をボロノイ境界と呼び、各々のボロノイ境界の交点をボロノイ点と呼ぶ。

特徴

ボロノイ図およびボロノイ領域は以下の特徴を有する。

ボロノイ領域は凸領域である。
ボロノイ点は、各々のボロノイ境界の母点から等距離の位置に存在している。特に二次元ユークリッド平面の場合、母点を中心とした円の交点となる。

応用

最近点探索：与えられた点に最も近い母点を探す問題は直接的にのみならず、複雑な問題の一部分としても現れ、ボロノイ領域を応用したデータ構造を構築することで素早く探すことができる^[2]。
ロボット動作計画：障害物を避けて目的地に到達することが可能であれば、障害物を母点とするボロネイ境界上に経路をとることができる。このように空間をより低次元の骨格に置き換える手法はレトラクション・アプローチ（retraction approach）と呼ばれる^[3]。
ドロネー三角形分割：ユークリッド平面上のボロノイ図において、もしいずれの4母点も同一円上に無ければ^{[注 1]}、ボロノイ領域が辺を共有する母点同士を線分で繋ぐことで母点全体の凸包をいくつかの三角形で分割したものが得られ、この三角形分割は理論・応用の両面において興味深い性質を持つ^[5]。
補間：有限の点集合 $P$ 上の値のみがわかっている関数のある点 $x$ での値を推測する方法の一つとして、 $P \cup {x}$ を母点とした際の $x$ のボロネイ領域について、 $P$ を母点とした際の $P$ の各点のボロネイ領域が占める割合で重みをつけて $P$ 上の関数値を足し上げる方法がある^[6]。

歴史

ボロノイ図の利用例は（きちんとそれが定式化される以前も含めれば）1644年のデカルトまで遡ることができる。ディリクレは1850年に二次形式についての自身の研究において、2次元と3次元のボロノイ図を用いている。このことから、ボロノイ図にはディリクレ空間分割（英: Dirichlet tessellation）の異称もある^[2]。

ボロノイ図の名はロシア人数学者ゲオルギ・フェドセビッチ・ボロノイ（英語版）に因んだもので、彼は1908年に一般の n-次元の場合を定義、研究した。地球物理学や気象学で（降雨量測定のような）空間分布データの解析に用いられるボロノイ図は、アメリカ人気象学者アルフレッド・H・ティーセン^enの名前を取って、ティーセン多角形（Thiessen polygon^en）と呼ばれている。凝縮系物理学ではボロノイ細胞はウィグナー=サイツ単位セル（Wigner-Seitz unit cell^en）として知られる。運動量の逆格子から得られるボロノイ図はブリルアンゾーン（Brillouin zone^en）と呼ばれる。リー群における一般格子に対し、そのボロノイ細胞のことを簡単に基本領域 (fundamental domain^en) と呼ぶ。一般距離空間の場合には、そのボロノイ細胞のことをしばしば計量基本多項式（metric fundamental polygon^en）と呼ぶ。