ボロノイ図（ティーセン多角形）

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

距離空間内の有限部分集合 P = {p1,p2,…,pn} および、距離関数 d に対して
V(p(i)) = {p | d(p,p(i)) ≦ d(p,p(j)) , j≠i}
で構成される領域 V(p(i)) を p(i) のボロノイ領域と呼ぶ。また、{V(p(1)),V(p(2)),…,V(p(n))} をボロノイ図と呼ぶ。
ボロノイ領域の境界をボロノイ境界と呼び、各々のボロノイ境界の交点をボロノイ点と呼ぶ。

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

ボロノイ図の名前は、1908年にn次元のボロノイ図について研究したロシアの数学者ゲオルギ・フェドセビッチ・ボロノイに由来する。
地球物理学や気象学で用いられるボロノイ図は、アメリカの気象学者アルフレッド・H・ティーセンの名前を取って、ティーセン多角形と呼ばれている。
また、一般的な距離空間では、metric fundamental polygonと呼ばれている。

画素の集合からなる平面上で考えたボロノイ図を離散ボロノイ図という。画素毎に最も近い母点へ所属させる。
離散ボロノイ図のボロノイ領域は多角形ではなく、画素の集合で表される。遠くから見ると通常のボロノイ図と同じに見える。
通常のボロノイ図では勢力分割線の交点を求めなければならないが離散ボロノイ図では任意の画素にとってどの画素が最も近いか決定すればよい。
その方法として母点のある画素から距離の順に母点の所属を決めていく波面法がわかりやすい。
通常のボロノイ図では母点が多くなると計算誤差の累積のためにアルゴリズムが破綻をきたすが、離散ボロノイ図ではアルゴリズムが簡単であるため破綻しにくい。

左画像：2次元ボロノイ図の一例。個々の色分けが一つの領域を表す。
右画像：3次元ボロノイ領域の断面図（領域は全て凸領域）。一般に、3次元ボロノイ領域の断面図は2次元ボロノイ図とはならない。

ttp://ja.wikipedia.org/wiki/%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3
ttp://en.wikipedia.org/wiki/Voronoi_diagram
ttp://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3
ttp://www.orsj.or.jp/~wiki/wiki/index.php/%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3
ttp://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E3%83%9C%E3%83%AD%E3%83%8E%E3%82%A4%E5%9B%B3%E3%80%8B

参照（未来の日記）：ドロネー図（双対はボロノイ図）
ttp://mixi.jp/view_diary.pl?id=713256156&owner_id=14882521

参照（関連サイト）：ボロノイ細胞と平行多面体（〜その２２）
ttp://www.geocities.jp/ikuro_kotaro/koramu/386_v.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/411_v2.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/412_v3.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/413_v4.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/415_v5.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/418_v6.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/420_v7.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/425_v8.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/431_v9.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/432_v10.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/434_v11.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/437_v12.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/454_v13.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/516_v14.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/517_v15.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/518_v16.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/519_v17.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/526_v18.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/527_v19.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/528_v20.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/529_v21.htm
ttp://www.geocities.jp/ikuro_kotaro/koramu/537_v22.htm