Metraipolis › archive › dc_e4e2dfd0553b

Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation — arXiv:2611.04829

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.04829
License (as archived): CC0-1.0
Archived: 2026-11-04T19:07:47.362Z
SHA-256 of the archived text: 2ec33e9c1bc71fb1a9aefdd5999a4b2d05c7857a8aa979e1c5df080bce3f2114
Stable URL of this page: https://metraipolis.com/documento/dc_e4e2dfd0553b

How to cite

Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation — arXiv:2611.04829 — arXiv (en), https://arxiv.org/abs/2611.04829 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e4e2dfd0553b (Metraipolis archive dc_e4e2dfd0553b, sha256 2ec33e9c1bc71fb1a9aefdd5999a4b2d05c7857a8aa979e1c5df080bce3f2114)

BibTeX

@misc{dce4e2dfd0553b,
  title = {Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation — arXiv:2611.04829},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.04829},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e4e2dfd0553b; sha256 2ec33e9c1bc71fb1a9aefdd5999a4b2d05c7857a8aa979e1c5df080bce3f2114},
  year = {2026}
}

Archived text

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

We study the geometric bin packing problem for simple polygonal regions, i.e., non-degenerate, connected, rational regions, in the minimum number of unit-square bins, allowing only translations. We even consider packing general non-convex objects, possibly with holes, where we can then pack smaller objects. Previous schemes cover squares (MOR'06), circles and other $L_p$-balls (Algorithmica'16), sufficiently skewed rectangles (Algorithmica'23), and convex fat objects with a constant number of distinct shapes under resource augmentation (arXiv'24, WAOA'23). The result for circles and other $L_p$-balls needs bin augmentation to obtain rational packing realizations. For restricted classes of $L$-shaped polygons, Gerlach et al. (SoCG'26) give constant worst-case guarantees, while for general non-convex objects, bounding-box reductions give just approximation factors that depend on fatness. Against this background, we present a general framework that provides asymptotic polynomial-time approximation schemes (APTAS) for bin packing of any fixed class of simple polygonal regions satisfying just two assumptions. First, covering any object by the grid cells intersecting its interior in any sufficiently fine square grid, relative to the object's bounding box, increases its area by at most a small fraction. Second, the class can be partitioned into a constant number of sequences such that each object in a sequence can be translated to fit inside every preceding object. In particular, certain classes of star-shaped polygons and more general polygonal regions, including some with simple holes, satisfy both assumptions. In addition, our framework does not require a bound on the objects' boundary complexity. We emphasize that our results require no bin augmentation whatsoever and yield explicit, exact rational packings of polynomial encoding length for all input objects.

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.04829 — 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-04T18:40:52.495Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).