ボロノイ図

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ボロノイ図（－ず 英:Voronoi diagram）とは、ある距離空間上の任意の位置に配置された複数個の点（母点）に対して、同一距離空間上の他の点がどの母点に近いかによって領域分けされた図のことである。特に二次元ユークリッド平面の場合、領域の境界線は、各々の母点の二等分線の一部になる。

目次 1 定義 2 歴史 3 特徴 4 応用 5 関連項目

[編集] 定義

距離空間内の有限部分集合 P = {p₁, p₂, ..., p_n} および、距離関数 d に対して

で構成される領域 V(p_i) を p_i のボロノイ領域と呼ぶ。また、{V(p₁), V(p₂), ..., V(p_n)} をボロノイ図と呼ぶ。

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

[編集] 歴史

ボロノイ図の利用例は（きちんとそれが定式化される以前も含めれば）1644年のデカルトまで遡ることができる。ディリクレは1850年に二次形式についての自身の研究において、2次元と3次元のボロノイ図を用いている。

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

[編集] 特徴

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

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

[編集] 応用

• 校区の設定
• 画像データの圧縮
• 離散データの集約

[編集] 関連項目

• ドロネー図
• 離散ボロノイ図
• 最近傍探索