Numerical studies of MacQueenʹs k-means algorithm for computing the centroidal voronoi tessellations

We study a probabilistic algorithm for the computation of the centroidal Voronoi tessellation which is a Voronoi tessellation of a given set such that the associated generating points are centroids (centers of mass) of the corresponding Voronoi regions. We discuss various issues related to the implementation of the algorithm and provide numerical results. Some measures to improve the performance are also presented.