Geometric bin packing method fits complex shapes without extra space
Geometric Bin Packing Beyond Convexity: Approximation Schemes without Augmentation
Computational GeometryData Structures and Algorithms
Summary
Packing irregular shapes tightly into square bins is often tricky, especially when shapes are not simple or have holes. The authors present a new method that can pack many types of complex polygon shapes into unit-square bins without needing extra space for adjustment. Their approach works by organizing shapes into sequences and using fine grid coverings to approximate packing without increasing area much. This method avoids previous needs for enlarged bins and produces efficient, exact packings in reasonable time.
What this means in practice
- •For manufacturing planners: Optimize layout of complex-shaped parts in standard-size packing units without extra space to reduce shipping volume and costs.
- •For robotic path planners: Use exact mathematical packing results for complex shapes to improve robot task layouts requiring arrangement of irregular objects in fixed areas.
Authors
Lucas de Oliveira Silva, Elisa Dell'Arriva, Flávio Keidi Miyazawa
Abstract
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.