ボロノイ図

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

ボロノイ図の一例個々の色分けが一つの領域を表す

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

[編集] 定義

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

$V(p_i) = \{p\ |\ d(p, p_i) \le d(p, p_j),\ j\ne i\}$

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

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

[編集] 歴史

ボロノイ図の利用例はデカルト（1644年）まで遡ることができる。ディリクレは二次形式の研究のために、2次元と3次元のボロノイ図を用いた。イギリスの医師であったジョン・スノーは、1854年、ソーホーでのコレラ流行を調査するため、ブロード通りの複数の井戸のボロノイ図を作図している。

ボロノイ図の名前は、1908年にn次元のボロノイ図について研究したロシアの数学者ゲオルギ・フェドセビッチ・ボロノイ (Georgy Fedoseevich Voronoi) に由来する。ボロノイ図は研究分野ごとに異なる用語で呼ばれている。地球物理学や気象学で用いられるボロノイ図は、アメリカの気象学者アルフレッド・H・シーセンの名前を取って、シーセン多角形と呼ばれている。凝縮系物理学ではウィグナー=サイツセルとして知られている。逆格子におけるボロノイ図はブルリアン帯と呼ばれる。リー群における一般的な格子群を基本領域と呼ぶ。一般的な距離空間では、metric fundamental polygonと呼ばれている。

[編集] 特徴

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

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

[編集] 応用

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

[編集] 関連項目

この項目「ボロノイ図」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。

"http://ja.wikipedia.org../../../%E3%83%9C/%E3%83%AD/%E3%83%8E/%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3.html" より作成

カテゴリ: 数学関連のスタブ項目 | 幾何学 | 図 | 数学に関する記事