Kissing polytopes
- We investigate the following question: How close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms. We provide nearly matching bounds on this distance and discuss its exact computation. We also give similar bounds for disjoint rational polytopes whose binary encoding length is prescribed.
| Author: | Antoine Deza, Shmuel Onn, Sebastian Pokutta, Lionel Pournin |
|---|---|
| Document Type: | Article |
| Parent Title (English): | SIAM Journal on Discrete Mathematics |
| Volume: | 38 |
| Issue: | 4 |
| Year of first publication: | 2024 |
| DOI: | https://doi.org/10.1137/24M1640859 |
