Kissing polytopes (Q6622740)

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.