Metraipolis › archive › dc_388c7baeb017

Stacking Stars: Minimum-Area Packing with and without Rotation — arXiv:2611.07100

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.07100
License (as archived)
CC0-1.0
Archived
2026-11-06T14:54:28.264Z
SHA-256 of the archived text
cea2f79e1b525cfdba67657d88a9e752828f9eb63664ad67a2340534fc512e29
Stable URL of this page
https://metraipolis.com/documento/dc_388c7baeb017

How to cite

Stacking Stars: Minimum-Area Packing with and without Rotation — arXiv:2611.07100 — arXiv (en), https://arxiv.org/abs/2611.07100 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_388c7baeb017 (Metraipolis archive dc_388c7baeb017, sha256 cea2f79e1b525cfdba67657d88a9e752828f9eb63664ad67a2340534fc512e29)
BibTeX
@misc{dc388c7baeb017,
  title = {Stacking Stars: Minimum-Area Packing with and without Rotation — arXiv:2611.07100},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07100},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_388c7baeb017; sha256 cea2f79e1b525cfdba67657d88a9e752828f9eb63664ad67a2340534fc512e29},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07100. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the problem of packing a given set of polygons into a minimum-area convex container, that is, placing them without overlap so as to minimize the area of their convex hull. Every previously known polynomial-time algorithm with a nontrivial approximation guarantee for packing polygons with arbitrary edge orientations required the polygons to be convex. In fact, an algorithm was not even known when every input polygon was a quadrilateral. We obtain such algorithms for the entire class of star-shaped polygons with unrestricted combinatorial complexity. The stars may be just translated or also rotated. In either case, we give an $O(\log n)$-approximation algorithm, where $n$ is the number of stars. Likewise, we get $O(\log n)$-approximation algorithms for bin and strip packing, assuming that the diameter of the stars is at most some (small) constant. Previous approximation algorithms for polygon packing focused on convex objects, and the analysis always relied on a density argument, i.e., if the area of the packed objects is at least a fraction $\rho$ of the area of the container, then we have a $(1/\rho)$-approximation. However, star-shaped polygons may need an arbitrarily large area to be packed, even when the total area of the stars approaches $0$ and each star has bounded diameter. This phenomenon prevents the use of density arguments. We instead establish a strong structural property about any packing: Even though the stars can fit together in complicated ways, we can reorganize them into simple stacks, replace these stacks by rectangles, and consider a packing of these rectangles. The rearrangement costs only a factor of $O(\log n)$, which stems from the number of size groups. We complement our algorithms by showing that both the translational and the rotational versions are APX-hard, even for constant complexity stars.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Computational Geometry (cs.CG) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.07100 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:26:57.634Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).