Kissing Polytopes
SIAM Journal on Discrete Mathematics · 31.12.2024 · 38 (4) · 2643-2664
DOI: 10.1137/24m1640859 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 09.10.2024. Verfasst von Antoine Deza und 3 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 14 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft, Natural Sciences and Engineering Research Council of Canada, Israel Science Foundation.
Abstract (Originalsprache)
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.
Förderung
- Deutsche Forschungsgemeinschaft
- Natural Sciences and Engineering Research Council of Canada
- Israel Science Foundation
- National Science Foundation
- Technion-Israel Institute of Technology
Zitieren
APA
Deza, A., Onn, S., Pokutta, S., & Pournin, L. (2024). Kissing Polytopes. SIAM Journal on Discrete Mathematics, 38(4), 2643-2664. https://doi.org/10.1137/24m1640859
Vancouver
Deza A, Onn S, Pokutta S, Pournin L. Kissing Polytopes. SIAM Journal on Discrete Mathematics. 2024;38(4):2643-2664. doi:10.1137/24m1640859
BibTeX
@article{Deza2024,
author = {Deza, Antoine and Onn, Shmuel and Pokutta, Sebastian and Pournin, Lionel},
title = {Kissing Polytopes},
journal = {SIAM Journal on Discrete Mathematics},
year = {2024},
volume = {38},
number = {4},
pages = {2643--2664},
doi = {10.1137/24m1640859}
}
EUVIMED