重心ボロノイ分割
幾何学における重心ボロノイ分割（英: centroidal Voronoi tessellation; CVT）とは、母点が領域の重心 (centroid) と一致するボロノイ図であり、母点の最適分布に対応する最適な領域分割として見ることができる。 K平均法のLloydアルゴリズムなどの多数のアルゴリズムをにより、重心ボロノイ分割を生成できる。
1次元と2次元では証明されているガーショの予想では、「漸近的には、最適な重心ボロノイ分割の全ての母点は、その次元の基本セルと一致する[1]」とされており、例えば2次元空間では、最適な重心ボロノイ分割の母点は正六角形となる。
重心ボロノイ分割は、データ圧縮・最適直交基底・最適量子化・クラスタリング・最適メッシュ生成などに用いられる[2]。自然界に見られる多くのパターンは、重心ボロノイ分割に非常に似ており、ジャイアンツ・コーズウェーの石柱・角膜の細胞[3]・雄のティラピア（カワスズメ）の縄張りなどがその1例である。
重み付き重心ボロノイ分割は、各重心（母点）が特定の関数に従って重み付けされた重心ボロノイ分割であり、デジタル点描の点の生成のために、グレースケール画像を重心ボロノイ分割の母点に重み付けする濃度関数として利用できる[4]。具体的には、濃い位置に多くの点が集まるように密度関数を定義して生成している。
正方形を5つの母点で分割する際の重心ボロノイ分割の例3種
出典[編集]
- ^ Du, Qiang; Wang, Desheng (2005), “The Optimal Centroidal Voronoi Tessellations and the Gersho's Conjecture in the Three-Dimensional Space”, Computers and Mathematics with Applications (49): 1355–1373
- ^ Du, Qiang; Faber, Vance; Gunzburger, Max (1999), “Centroidal Voronoi Tessellations: Applications and Algorithms”, SIAM Review 41 (4): 637–676, doi:10.1137/S0036144599352836.
- ^ Pigatto, João Antonio Tadeu (2009). “Scanning electron microscopy of the corneal endothelium of ostrich”. Cienc. Rural 39 (3): 926–929. doi:10.1590/S0103-84782009005000001.
- ^ Secord, Adrian. "Weighted voronoi stippling." Proceedings of the 2nd international symposium on Non-photorealistic animation and rendering. ACM, 2002.