Small Kissing Polytopes

A lattice (d, k)-polytope is the convex hull of a set of points in Rd$$\mathbb {R}^d$$ whose coordinates are integers ranging between 0 and k. We consider the smallest possible distance ε(d,k)$$\varepsilon (d,k)$$ between two disjoint lattice (d, k)-polytopes. We propose an algebraic model for this distance and derive from it an explicit formula for ε(2,k)$$\varepsilon (2,k)$$. Our model also allows for the computation of previously intractable values of ε(d,k)$$\varepsilon (d,k)$$. In particular, we compute ε(3,k)$$\varepsilon (3,k)$$ when 4≤k≤8$$4\le {k}\le 8$$, ε(4,k)$$\varepsilon (4,k)$$ when 2≤k≤3$$2\le {k}\le 3$$, and ε(6,1)$$\varepsilon (6,1)$$.