EUVIMEDEUVIMED entdecken
Crossref

Kissing Polytopes

Antoine Deza, Shmuel Onn, Sebastian Pokutta, Lionel Pournin

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.

AbstractBibliografische AngabenZitieren

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}
}
Kostenlos starten →