Computation of Centroidal Voronoi Tessellations in High Dimensional Spaces
Computation of Centroidal Voronoi Tessellations in High Dimensional Spaces
复制标题
DOI：
10.1109/lcsys.2022.3185032
复制
发表时间：
2022-03
影响因子：
3
通讯作者：
B. Telsang;Seedik M Djouadi
中科院分区：
文献类型：
--
作者：
B. Telsang;Seedik M Djouadi
由于自然的解释和各种理想的数学性质，质心Voronoi镶嵌（CVT）已经找到了广泛的应用和相应的巨大发展，在他们的文献。然而，在高维空间中的CVT的计算仍然是困难的。在这封信中，我们利用非唯一性的CVTs在高维空间的计算。我们通过在一维空间中分解成CVT来构建这种高维镶嵌。然后，我们证明了在一维空间上密度独立的条件下，这种镶嵌是重心的。各种数值计算通过网格状镶嵌的低能量来支持理论结果，并且以最小的计算时间获得。我们还比较了建议的分解方法与流行的MacQueen的概率方法。
Owing to the natural interpretation and various desirable mathematical properties, centroidal Voronoi tessellations (CVTs) have found a wide range of applications and correspondingly a vast development in their literature. However, the computation of CVTs in higher dimensional spaces remains difficult. In this letter, we exploit the non-uniqueness of CVTs in higher dimensional spaces for their computation. We construct such high dimensional tessellations by decomposing into CVTs in one-dimensional spaces. We then prove that such a tessellation is centroidal under the condition of independence among densities over the 1-D spaces. Various numerical evaluations backup the theoretical result through the low energy of the grid-like tessellations, and are obtained with minimal computation time. We also compare the proposed decomposition method with the popular MacQueen’s probabilistic method.