Bounds on the geometric complexity of optimal centroidal Voronoi tesselations in 3D

DOI10.1007/S00220-020-03789-YMaRDI QIDQ779651zbMATH OpenOpenAlexFDO

Authors Rustum Choksi, Xin Yang Lu

Publication date 14 July 2020

Published in Communications in Mathematical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.07591

zbMATH Keywords

asymptotic periodicitygeometric complexity3D Gersho's conjectureoptimal centroidal Voronoi tessellations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial complexity of geometric structures (52C45)

Abstract: Gersho's conjecture in 3D asserts the asymptotic periodicity and structure of the optimal centroidal Voronoi tessellation. This relatively simple crystallization problem remains to date open. We prove bounds on the geometric complexity of optimal centroidal Voronoi tessellations which, combined with an approach introduced by Gruber in 2D, reduce the resolution of the 3D Gersho's conjecture to a finite (albeit large) computation of an explicit convex problem in finitely many variables.

Recommendations

• The optimal centroidal Voronoi tessellations and the Gersho's conjecture in the three-dimensional space
• Centroidal Voronoi Tessellations: Applications and Algorithms
• scientific article; zbMATH DE number 6164563
• Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
• The dodecahedral conjecture

Cites work

• scientific article; zbMATH DE number 1332581 (Why is no real title available?)
• scientific article; zbMATH DE number 1153207 (Why is no real title available?)
• scientific article; zbMATH DE number 3083197 (Why is no real title available?)
• A proof of crystallization in two dimensions
• A short analytic proof of Fejes Tóth's theorem on sums of moments
• Asymptotic quantization error of continuous signals and the quantization dimension
• Asymptotically optimal block quantization
• Centroidal Voronoi Tessellations: Applications and Algorithms
• Convex and Discrete Geometry
• Crystallization for a Brenner-like potential
• Face-centered cubic crystallization of atomistic configurations
• On the crystallization of 2D hexagonal lattices
• Optimal Transport
• Optimum quantization and its applications
• The Optimal Lattice Quantizer in Three Dimensions
• The crystallization conjecture: a review
• The expected number of \(k\)-faces of a Voronoi diagram
• The hexagon theorem
• The honeycomb conjecture
• The optimal centroidal Voronoi tessellations and the Gersho's conjecture in the three-dimensional space
• The sphere packing problem in dimension 8
• The sphere packing problem in dimension \(24\)

Cited in

(6)

• The optimal centroidal Voronoi tessellations and the Gersho's conjecture in the three-dimensional space
• A simple geometric method for navigating the energy landscape of centroidal Voronoi tessellations
• scientific article; zbMATH DE number 7325770 (Why is no real title available?)
• Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
• Asymptotic optimality of the triangular lattice for a class of optimal location problems
• On The Characterization and Uniqueness of Centroidal Voronoi Tessellations

This page was built for publication: Bounds on the geometric complexity of optimal centroidal Voronoi tesselations in 3D

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q779651)