Date & Time: Thursday, October 9, 2025 at 4:30 PM
Location: 101 - Sherrerd Hall
Speaker: Antoine Deza, McMaster University
Title: Integrality properties of kissing polytopes distances
Abstract: A lattice (d,k)-polytope is the convex hull of a set of points in dimension d whose coordinates are integers ranging from 0 to k. We investigate the smallest possible distance between two disjoint lattice (d,k)-polytopes. A pair of polytopes achieving this minimal distance are called kissing polytopes. This question arises in various contexts where the minimal distance between such polytopes appears in complexity bounds for optimization algorithms. We provide nearly matching lower and upper bounds for this distance and propose an algebraic model. Our formulation yields explicit formulas in dimensions 2 and 3, and allows for the computation of previously intractable values. We also discuss related results, such as the Alon–Vu bounds for flat simplices — that is, the minimum distance between a vertex of a lattice (d,1)-simplex and the affine space spanned by the remaining vertices. Finally, we observe that all the known squared distances between kissing polytopes are inverses of integers, and we ask whether this observation holds in general. Based on joint-work with Shmuel Onn (Technion), Sebastian Pokutta (Zuse Institute Berlin and TU Berlin), and Lionel Pournin (Université Paris 13).