Kissing polytopes

DOI10.1137/24M1640859MaRDI QIDQ6622740zbMATH OpenFDO

Authors Antoine Deza, Shmuel Onn, Sebastian Pokutta, Lionel Pournin

Publication date 22 October 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/24M1640859

zbMATH Keywords

alternating projectionsdistances in geometric latticesfacial distancelattice polytopespyramidal widthvertex-facet distance

Mathematics Subject Classification ID

Geometric constructions in real or complex geometry (51M15) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Lattices and convex bodies in (n) dimensions (aspects of discrete geometry) (52C07)

Review text

Let \(P\) and \(Q\) be polytopes with vertices in \(\{ 0, 1, \dots, k \}^d\). The main results of the paper under review give the lower bound for the distance between \(P\) and \(Q\) \N\[\Nd(P, Q) \ge \frac{1}{(kd)^{2d}},\N\]\Nand the existence of \(P\) and \(Q\), for \(d\) large enough, such that \N\[\Nd(P, Q) \le\frac{1}{(k \sqrt d)^{\sqrt d}}.\N\]\NConsequently, the minimum of the facial distance (i.e., the distance between two faces that belong to distinct parallel hyperplanes) over all lattice polytopes \(P, Q \in [0,k]^d\) has the same lower and upper bound as above. The question of how close two lattice polytopes contained in a fixed cube can be stems from various complexity bounds of optimization algorithms.

Recommendations

• Geometric comparison of combinatorial polytopes
• Distances to lattice points in knapsack polyhedra
• Distance between vertices of lattice polytopes
• scientific article; zbMATH DE number 4115426

Cites work

• Anti-Hadamard matrices
• Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
• Geometric algorithms and combinatorial optimization.
• scientific article; zbMATH DE number 1234104 (Why is no real title available?)
• Linearly convergent away-step conditional gradient for non-strongly convex functions
• Mixed-integer quadratic programming is in NP
• Polytope conditioning and linear convergence of the Frank-Wolfe algorithm
• Quadratic programming is in NP
• The condition number of a function relative to a set
• The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes

Cited in

(1)

• Small kissing polytopes

This page was built for publication: Kissing polytopes

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