2D Strip Packing

Definition

Pack axis-aligned rectangles into a strip of fixed width and unbounded height, without overlap, minimizing the used height.

Example

Suppose a strip of width $W = 4$ and items: one $4\times1$ and two $2\times3$. Placing the two $2\times3$ pieces side by side fills the width ($2+2=4$) at height 3, and the $4\times1$ on top brings the used height to 4. This matches the lower bound — total area $6+6+4=16$ divided by width 4 — so it is optimal.

Relationship to irregular nesting

Strip packing is the orthogonal special case of the broader nesting problem: when every piece is a rectangle, irregular nesting reduces to strip packing. They share constructive placement heuristics (notably bottom-left), recorded as an E2_method_shared link rather than an equivalence — the geometry differs even though the methodology overlaps.

Benchmarks

Unlike irregular nesting (for which 2DPackLib is only adjacent), 2DPackLib is a direct benchmark here: it targets two-dimensional orthogonal cutting and packing. [grade A]

Related nodes

See the depth-1 graph below.