ボロノイ図 - 情報科学と人工知能のノート

距離空間とその中の複数個の点（母点、seed などと呼ばれます）が与えられたときに、空間上の各点が与えられたどの点に最も近いかを分類した図をボロノイ図といいます．
与えられた距離空間を $(X, d)$ 、与えられた点を $x_1, \cdots, x_k \in X$ とおいて数式で書くと点 $x_i$ に対応する領域は $\{ x \in X \ | \ d(x, x_i) \leq d(x, x_j) \ \mbox{for all j \neq i}\}$ となります．与える点を $X$ の部分空間に拡張することもできます．当然、距離関数にはユークリッド距離以外を使うこともできます．

応用

ボロノイ図は機械学習や物理学や化学や古くは疫学など非常に多くの分野で使用されているらしいのですが、いきなり単体で出てくると正直「で？」となるのではないでしょうか．僕自身そう思い、かといって応用として自分の研究に出てくることもなく、ずっと敬遠していたのですが、画像やテクスチャの自動生成に応用できるということで非常に興味が湧きました．

次の図は A Survey of Procedural Techniques for City Generation（Kelly et al., 2006, Institute of Technology Blanchardstown Journal）の図 15 からの引用です．
f:id:ti2236:20130106172332p:plain
一番左は石畳かなにかで、二番目はおそらく樹木の表皮です．三番目はなんだか分かりませんが生化学的ななにかでしょうか．いずれの画像もボロノイ図を加工して自動生成された画像です．

また、次の図は A Method for Creating Mosaic Images Using Voronoi Diagrams （Dobashi, et al., EUROGRAPHICS 2002）の図 7 の a からの引用です．
f:id:ti2236:20130106172344p:plain
こちらは与えられた画像に対して点をばらまき、その点に対するボロノイ図を加工することによって生成された、ステンドグラスのようなモザイク画像です．

どちらもいずれ独立した記事で解説しようと思います．