Centroidal Voronoi tessellation (重心ボロノイ分割)

Centroidal Voronoi tessellation (重心ボロノイ分割) とは、分割後の領域の重心と母点が一致するボロノイ分割のこと。

そもそもボロノイ分割ってなんだっけ？

ボロノイ分割とは、ある領域（例えば2次元平面上の四角形）を、複数の領域に分割する方法の1つ。
複数の点をばらまいて、もっとも近い場所にある2点の中間に境界を定める。
その結果、次のような分割ができる。

入力（母点と呼ぶ）

ボロノイ分割

よく見ると次のようなことがわかる。
「どの母点に最も近いか」という観点で領域分けした結果に等しい。

そもそも、これがボロノイ分割の定義。

母点を国の首都としたときの、各国の勢力図のようなものと考えるといい。
「ある地点は、そこから最も近くに首都がある国の領土になる」とすれば、その結果はボロノイ分割となる。

さてここで、もう一度確認。
Centroidal Voronoi tessellation (重心ボロノイ分割) とは、分割後の領域の重心と母点が一致するボロノイ分割のこと。
母点が最も効率的に分布したときの分割方法とみなすことができる。

これは、一般的なボロノイ分割から、次の(1)と(2)を繰り返すことで得られる。

(1) ボロノイ分割した後の、各領域の重心を求める。
(2) 母点を重心に移動して、もう一度ボロノイ分割する。

これを繰り返すと、最終的に、重心ボロノイ分割に収束する。

このような繰り返しは Lloyd's algorithm と呼ばれていて、クラスタリングで用いられる k-means法でも用いられる。
ボロノイ分割に適用すると、次のように分割結果が変化する。

図中の●は母点、＋は重心

次のリンク先では、この繰り返し処理の様子を動画で見ることができる。

■Centroidal Voronoi Tessellation (by Kaisei Hamamoto) | vimeo
http://vimeo.com/6551478

なわばりの数理モデル -ボロノイ図からの数理工学入門-

コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用