Abstract
Voronoi tessellation was known a long time ago. A centroidal Voronoi tessellation (CVT) is a special type of Voronoi tessellation that the Voronoi points (generators) are mass centers of the corresponding Voronoi regions. This brings the optimization properties to CVT and the properties can be applied to problems of image compression, optimal quadrature rules, etc. This paper is concerned with the methods of finding CVT. First, some properties and theoretical results of CVT are shown. Since it is difficult to find the CVT theoretically in general, k-means method and Lloyd method will be introduced so that we can find the CVT numerically. The efficiency and the accuracy of both methods will be compared.