Small kissing polytopes

Abstract

A lattice $(d,k)$-polytope is the convex hull of a set of points in ${\mathbb{R}}^d$ whose coordinates are integers ranging between $0$ and $k$. We consider the smallest possible distance $\epsilon (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 $\epsilon (2,k)$. Our model also allows for the computation of previously intractable values of $\epsilon (d,k)$. In particular, we compute $\epsilon (3,k)$ when $4\le k\le 8$, $\epsilon (4,k)$ when $2\le k\le 3$, and $\epsilon (6,1)$.

17 pages, 2 figures