MinMax Arena
中/EN
P81 · Packing and covering · Classic · Applied frontier

Irregular strip nesting

VERIFIED CONSTRUCTIONoccupied length 47319.411
GARDEYN2 · 50 pieces, all differentCurrent record · open

Given the strip height H, a set of piece polygons and how many copies of each are demanded, place every piece in the strip so that the largest x-coordinate over all vertices — the occupied length L — is as small as possible. Pieces may only be translated and turned about their own origin by 0°, 90°, 180° or 270°; they may touch but their interiors may not overlap, and none may leave the strip.

Formal definition

  • ContainerThe closed region {x ≥ 0, 0 ≤ y ≤ H}; a piece may touch the boundary. H is fixed per case: 20000 for GARDEYN1, 10000 for GARDEYN2, 44 for GARDEYN9
  • SubmissionOne placement per copy of a piece: its type, its turn and its shift. The piece polygons (concave and asymmetric allowed), the demands and the strip height are frozen by the case; a submission changes no vertex, count or shape
  • MovesEach copy is turned about its own origin by 0°, 90°, 180° or 270°, then shifted by (x, y). No reflection, scaling or free angle
  • No overlapNo two copies have intersecting interiors: touching along an edge or at a vertex is allowed; containment or any positive-area overlap is not
  • Exact verificationCoordinates are decimal strings of at most 24 places, scaled by 10²⁴ to integers, and the four right-angle turns keep them integers. Every polygon is triangulated exactly and every triangle pair is tested by separating axes with BigInt cross products; equal projection endpoints are contact, not overlap. No floating point and no ε
  • ScoreThe largest x-coordinate over all placed vertices, L, exact to 24 places; smaller is better. The source file's container length is not the score, and a claimed score is ignored
  • ObjectiveMinimise L over all legal placements

Getting a feel for it

Why these three cases

The GARDEYN family comes from real garment-cutting and direct-to-film print jobs: concave, asymmetric outlines with few repeats. GARDEYN1 is 10 types, 5 copies each; GARDEYN2 is 50 pieces, all different; GARDEYN9 is 47 different print motifs in a strip only 44 high. Each case is complete on its own, and an answer for one says nothing about another.

Quarter turns only

Nesting solvers in the literature usually allow continuous rotation, but continuous angles carry trigonometry into the coordinates and cannot be verified exactly. Here only 0°, 90°, 180° and 270° are allowed, every coordinate stays rational, and the verifier decides contact and overlap with no tolerance at all. It also means this problem is not directly comparable with published results that allow free rotation.

Where the frontier is

There is no external record. The Sparrow repository publishes its own layouts (lengths 16181.169, 47382.125 and 65.792223), each of which verifies exactly under this problem's rules; starting from them, a short exact compaction here brought the three cases to 16177.649, 47319.670679 and 65.769735999999999, shipped as baselines bylined MinMax Arena. None of these is a proof of optimality or a literature record; the editor can load Sparrow's layouts and the weaker 20-second starting layouts for comparison.

Source

Where the data comes from

The instance geometry and the reference layouts come from the Sparrow repository (Jeroen Gardeyn, Greet Vanden Berghe and Tony Wauters, KU Leuven; MIT) at revision 649d4c78, with the original decimal coordinates kept free of floating-point truncation; each case's input hashes and source links can be downloaded from the editor.

Source
ONE LEADERBOARD PER n

Current best solutions by n

Each n is an independent record with a page of its own. Open any of them to inspect the current construction, then challenge it.

Discussion (1) ↓
InstanceGARDEYN1 · 50 pieces, 10 types
CURRENT RECORD16176.8923
Hard
Record holderNUE_13
Solution methodHuman
InstanceGARDEYN2 · 50 pieces, all different
CURRENT RECORD47319.410679
Hard
Record holderNUE_13
Solution methodHuman
InstanceGARDEYN9 · 47 pieces, all different
CURRENT RECORD65.769735999999999
Hard
Answer sourceMinMax Arena
Solution methodMinMax Arena offline search

Data and citation

Every sub-problem in this family — authoritative scores, proof status, coordinates and sources — lives at the stable address below, published under CC BY 4.0. Scores move as records fall, so cite the generatedAt timestamp the file carries.

GET https://minmaxarena.com/data/irregular-strip-nesting.json

Cite the frozen 2026-08 edition: records move, a frozen edition never does, so the citation is still checkable years later.

GET https://minmaxarena.com/data/editions/2026-08/irregular-strip-nesting.json
BibTeX (click to copy)
@misc{minmaxarena-irregular-strip-nesting-2026-08,
  title  = {{Irregular strip nesting} (P81)},
  author = {{MinMax Arena}},
  year   = {2026},
  note   = {Machine-verified records, 2026-08 edition},
  url    = {https://minmaxarena.com/data/editions/2026-08/irregular-strip-nesting.json},
  license = {CC BY 4.0}
}
DISCUSSION

Discussion

Talk strategy, share methods, ask why you are stuck. Every signed-in user can post. Posts carry your public byline, the same name your records use; the #number after it is the account's signup ordinal, so a name cannot be worn by someone else. New posts appear after an automated review.

问题大草NUE_13#310 replies