Kissing Polytopes
1 : McMaster University
2 : Technion - Israel Institute of Technology
3 : Zuse Institute Berlin
4 : Université Paris 13
Add this new organization
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 stems from 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.
- Poster