Packing d-dimensional balls into a d+1-dimensional container
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914062808383488 |
|---|---|
| author | Alt, Helmut Cabello, Sergio Cheong, Otfried Park, Ji-won Seiferth, Nadja |
| author_facet | Alt, Helmut Cabello, Sergio Cheong, Otfried Park, Ji-won Seiferth, Nadja |
| contents | In this article, we consider the problems of finding in $d+1$ dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of $d$-dimensional unit-radius balls can be packed under translations. The computational problem is neither known to be NP-hard nor to be in NP. We give a constant-factor approximation algorithm for each of these containers based on a reduction to finding a shortest Hamiltonian path in a weighted graph, which in turn models the problem of stabbing the centers of the input balls while keeping them disjoint. We also show that for $n$ such balls, a container of volume $O(n^{\frac{d-1}{d}})$ is always sufficient and sometimes necessary. As a byproduct, this implies that for $d \geq 2$ there is no finite size $(d+1)$-dimensional convex body into which all $d$-dimensional unit-radius balls can be packed simultaneously. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2110_12711 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Packing d-dimensional balls into a d+1-dimensional container Alt, Helmut Cabello, Sergio Cheong, Otfried Park, Ji-won Seiferth, Nadja Computational Geometry Metric Geometry In this article, we consider the problems of finding in $d+1$ dimensions a minimum-volume axis-parallel box, a minimum-volume arbitrarily-oriented box and a minimum-volume convex body into which a given set of $d$-dimensional unit-radius balls can be packed under translations. The computational problem is neither known to be NP-hard nor to be in NP. We give a constant-factor approximation algorithm for each of these containers based on a reduction to finding a shortest Hamiltonian path in a weighted graph, which in turn models the problem of stabbing the centers of the input balls while keeping them disjoint. We also show that for $n$ such balls, a container of volume $O(n^{\frac{d-1}{d}})$ is always sufficient and sometimes necessary. As a byproduct, this implies that for $d \geq 2$ there is no finite size $(d+1)$-dimensional convex body into which all $d$-dimensional unit-radius balls can be packed simultaneously. |
| title | Packing d-dimensional balls into a d+1-dimensional container |
| topic | Computational Geometry Metric Geometry |
| url | https://arxiv.org/abs/2110.12711 |