重心ボロノイ分割

正方形内の5点の3つの重心ボロノイ分割

幾何学において、重心ボロノイ分割（CVT ）は、各ボロノイセルの生成点が重心（質量の中心）でもある特殊なタイプのボロノイ分割である。これは、生成元の最適分布に対応する最適なパーティションとして見ることができる。重心ボロノイ分割を生成するために使用できるアルゴリズムは多数あり、その中にはK平均法クラスタリングのロイドのアルゴリズムやBFGSのような準ニュートン法が含まれる。 ^[1]

証明

1次元と2次元で証明されたガーショの予想は、「漸近的に言えば、最適なCVTのすべてのセルは、タイル張りを形成しながら、次元に依存する基本セルと一致する」と述べています。 ^[2]

2 次元では、最適な CVT の基本セルは正六角形です。これは、2D ユークリッド空間で円が最も密に詰め込まれたものであることが証明されているためです。3 次元では、これに相当するのは菱形十二面体ハニカムで、3D ユークリッド空間で球が最も密に詰め込まれたものから派生したものです。

アプリケーション

重心ボロノイ分割は、データ圧縮、最適求積、最適量子化、クラスタリング、最適メッシュ生成に役立ちます。 ^[3]

重み付き重心ボロノイ図は、各重心が特定の関数に従って重み付けされるCVTです。たとえば、グレースケール画像を密度関数として使用してCVTのポイントに重みを付け、デジタル点描を作成することができます。^[4]

自然界での発生

自然界に見られる多くのパターンは、重心ボロノイ分割によって近似されます。例としては、ジャイアンツ・コーズウェイ、角膜細胞^{[5] 、オスの}ティラピアの繁殖ピット^[3]などが挙げられます。

参考文献

^ Nocedal, Jorge; Wright, Stephen J. (2006).数値最適化. Springer Series in Operations Research and Financial Engineering (第 2 版). Springer. doi :10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1。
^ Du, Qiang; Wang, Desheng (2005)、「3次元空間における最適重心ボロノイ分割とGershoの予想」、Computers and Mathematics with Applications、49 (9–10): 1355–1373、doi : 10.1016/j.camwa.2004.12.008
^ ab Du, Qiang; Faber, Vance ; Gunzburger, Max (1999)、「Centroidal Voronoi Tessellations: Applications and Algorithms」、SIAM Review、41 (4): 637–676、Bibcode :1999SIAMR..41..637D、CiteSeerX 10.1.1.452.2448、doi :10.1137/S0036144599352836 。
^ Secord, Adrian. 「重み付けボロノイ点描」。非フォトリアリスティックアニメーションとレンダリングに関する第 2 回国際シンポジウムの議事録。ACM、2002 年。
^ Pigatto, João Antonio Tadeu; et al. (2009). 「ダチョウの角膜内皮の走査型電子顕微鏡検査」Cienc. Rural . 39 (3): 926–929. doi : 10.1590/S0103-84782009005000001 . hdl : 11449/29422 .

[1] Nocedal, Jorge; Wright, Stephen J. (2006).数値最適化. Springer Series in Operations Research and Financial Engineering (第 2 版). Springer. doi :10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1。

[2] Du, Qiang; Wang, Desheng (2005)、「3次元空間における最適重心ボロノイ分割とGershoの予想」、Computers and Mathematics with Applications、49 (9–10): 1355–1373、doi : 10.1016/j.camwa.2004.12.008

[Du_2-3] Du, Qiang; Faber, Vance ; Gunzburger, Max (1999)、「Centroidal Voronoi Tessellations: Applications and Algorithms」、SIAM Review、41 (4): 637–676、Bibcode :1999SIAMR..41..637D、CiteSeerX 10.1.1.452.2448、doi :10.1137/S0036144599352836 。

[4] Secord, Adrian. 「重み付けボロノイ点描」。非フォトリアリスティックアニメーションとレンダリングに関する第 2 回国際シンポジウムの議事録。ACM、2002 年。

[5] Pigatto, João Antonio Tadeu; et al. (2009). 「ダチョウの角膜内皮の走査型電子顕微鏡検査」Cienc. Rural . 39 (3): 926–929. doi : 10.1590/S0103-84782009005000001 . hdl : 11449/29422 .