Folding One Polyhedral Metric Graph into Another
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929641389817856 |
|---|---|
| author | Chung, Lily Demaine, Erik D. Demaine, Martin L. Hecher, Markus Lin, Rebecca Lynch, Jayson Nara, Chie |
| author_facet | Chung, Lily Demaine, Erik D. Demaine, Martin L. Hecher, Markus Lin, Rebecca Lynch, Jayson Nara, Chie |
| contents | We analyze the problem of folding one polyhedron, viewed as a metric graph of its edges, into the shape of another, similar to 1D origami. We find such foldings between all pairs of Platonic solids and prove corresponding lower bounds, establishing the optimal scale factor when restricted to integers. Further, we establish that our folding problem is also NP-hard, even if the source graph is a tree. It turns out that the problem is hard to approximate, as we obtain NP-hardness even for determining the existence of a scale factor 1.5-ε. Finally, we prove that, in general, the optimal scale factor has to be rational. This insight then immediately results in NP membership. In turn, verifying whether a given scale factor is indeed the smallest possible, requires two independent calls to an NP oracle, rendering the problem DP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15121 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Folding One Polyhedral Metric Graph into Another Chung, Lily Demaine, Erik D. Demaine, Martin L. Hecher, Markus Lin, Rebecca Lynch, Jayson Nara, Chie Computational Geometry Computational Complexity Discrete Mathematics Symbolic Computation 68R10, 68Q17, 68U05 G.2.2; F.2.2 We analyze the problem of folding one polyhedron, viewed as a metric graph of its edges, into the shape of another, similar to 1D origami. We find such foldings between all pairs of Platonic solids and prove corresponding lower bounds, establishing the optimal scale factor when restricted to integers. Further, we establish that our folding problem is also NP-hard, even if the source graph is a tree. It turns out that the problem is hard to approximate, as we obtain NP-hardness even for determining the existence of a scale factor 1.5-ε. Finally, we prove that, in general, the optimal scale factor has to be rational. This insight then immediately results in NP membership. In turn, verifying whether a given scale factor is indeed the smallest possible, requires two independent calls to an NP oracle, rendering the problem DP-complete. |
| title | Folding One Polyhedral Metric Graph into Another |
| topic | Computational Geometry Computational Complexity Discrete Mathematics Symbolic Computation 68R10, 68Q17, 68U05 G.2.2; F.2.2 |
| url | https://arxiv.org/abs/2412.15121 |