Résumé : A lattice (d,k)-polytope is the convex hull of a set of points in dimension d whose coordinates are integers ranging between 0 and k. We investigate the smallest possible distance between two disjoint lattice (d,k)-polytopes. This question arises in various contexts where the minimal distance between such polytopes appears in complexity bounds of 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. Based on joint-work with Shmuel Onn (Technion), Sebastian Pokutta (Zuse Institute Berlin), and Lionel Pournin (Université Paris 13).

Dernière modification : Tuesday 28 January 2025

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr