Centroidal Voronoi Tessellations and Gersho’s conjecture in 3D

Centroidal Voronoi Tessellations (CVT) are tessellations using Voronoi regions of their centroids. CVTs are useful in several fields, such as data compression, optimal quadrature, optimal quantization, clustering, and optimal mesh generation. Many patterns seen in nature are closely approximated by a CVT. Examples include the Giant’s Causeway, the cells of the cornea, and the breeding pits of the male tilapia.
Gersho’s conjecture, which states that there exists an asymptotically optimal CVT whose Voronoi regions are all rescaled copies of the same polytope. Straightforward in 1D, and proven in 2D, Gersho’s conjecture is still open for higher dimensions. One of the main difficulties is that Gersho’s conjecture is a strongly nonlocal, infinite dimensional minimization problem (even in 3D). In this talk we will present some recent results which reduce Gersho’s conjecture to a local, finite dimensional problem in 3D. Joint work with Rustum Choksi.