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

DOI10.1007/S00220-020-03789-YzbMATH Open1443.52021arXiv1806.07591OpenAlexW3035134102MaRDI QIDQ779651FDOQ779651

Authors: Rustum Choksi, Xin Yang Lu 

Publication date: 14 July 2020

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)