ON THE CHARACTERIZATION AND UNIQUENESS OF CENTROIDAL VORONOI TESSELLATIONS

Vector quantization is a classical signal-processing technique with significant applications in data compression, pattern recognition, clustering, and data stream mining. It is well known that for critical points of the quantization energy, the tessellation of the domain is a centroidal Voronoi tessellation. However, for dimensions greater than one, rigorously verifying a given centroidal Voronoi tessellation is a local minimum can prove difficult. Using variational techniques, we give a full characterization of the second variation of a centroidal Voronoi tessellation and give sufficient conditions for a centroidal Voronoi tessellation to be a local minimum. In addition, the conditions under which a centroidal Voronoi tessellation for a given density and domain is unique have been elusive for dimensions greater than one. We prove that there does not exist a unique two generator centroidal Voronoi tessellation for dimensions greater than one.