Optimal Quantization and Centroidal Voronoi Tessellations

Nonconvex and nonlocal variational problems are pervasive in energy-driven pattern formation. Two central issues are:
(Q1) can one conjecture and prove asymptotic statements on the (geometric) nature of global minimizers.
(Q2) can one develop systematic, hybrid numerical algorithms to navigate (or probe) the energy landscape and access low energy states whose basin of attraction might be "tiny".

In this talk, we will mostly explore (Q1) in the context of the simple, yet rich, paradigm of optimal quantization and optimal centroidal Voronoi tessellations (CVT) on a 3D Euclidean domain and the 2-sphere. Gersho's conjecture, which may be viewed as a crystallization conjecture, asserts the periodic structure, as the number of generators tends to infinity, of the optimal CVT. In joint work with Xin Yang Lu (Lakehead University) we present certain bounds which, combined with a 2D approach of P. Gruber (following L. Fejers Toth), reduce the resolution of the 3D Gersho's conjecture to a finite (albeit very large) computation of an explicit convex problem in finitely many variables.

We then discuss the analogous problem on the 2-sphere.

We further address and support some interesting numerical observations about defect structures vs. lattice CVTs for the optimal CVT with a "small" number of generators on the 2D square torus. This is joint work with I. Gonzalez, C, Mantos, J. Tisdell and JC Nave at McGill.

Finally (time permitting), we will mention work (with I. Gonzalez and JC Nave) pertaining to issue (Q2) by presenting a new hybrid algorithm which alternates gradient descent with movement away from the closest generator.