Computation of Centroidal Voronoi Tessellations in High Dimensional Spaces

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.

Automated summary

This article presents a method for computing centroidal Voronoi tessellations in higher dimensional spaces, and proves that such tessellations can be efficiently computed under certain conditions. Numerical evaluations and comparisons with other methods validate the feasibility and efficiency of the proposed method.