Approximation Depth of Convex Polytopes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909682816253952 |
|---|---|
| author | Bakaev, Egor Brunck, Florestan Yehudayoff, Amir |
| author_facet | Bakaev, Egor Brunck, Florestan Yehudayoff, Amir |
| contents | We study approximations of polytopes in the standard model for computing polytopes using Minkowski sums and (convex hulls of) unions. Specifically, we study the ability to approximate a target polytope by polytopes of a given depth. Our main results imply that simplices can only be ``trivially approximated''. On the way, we obtain a characterization of simplices as the only ``outer additive'' convex bodies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07779 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximation Depth of Convex Polytopes Bakaev, Egor Brunck, Florestan Yehudayoff, Amir Metric Geometry Computational Geometry Machine Learning Combinatorics We study approximations of polytopes in the standard model for computing polytopes using Minkowski sums and (convex hulls of) unions. Specifically, we study the ability to approximate a target polytope by polytopes of a given depth. Our main results imply that simplices can only be ``trivially approximated''. On the way, we obtain a characterization of simplices as the only ``outer additive'' convex bodies. |
| title | Approximation Depth of Convex Polytopes |
| topic | Metric Geometry Computational Geometry Machine Learning Combinatorics |
| url | https://arxiv.org/abs/2507.07779 |