Return to Answer

A proof that packing under translation of rectangles is NP-complete is given by Richard Korf, Optimal Rectangle Packing: Initial Results. See also this talk by Helmut Alt _{(search for "PAR is NP-complete")}.

A proof that packing under translation of rectangles is NP-complete is given by Richard Korf, Optimal Rectangle Packing: Initial Results. See also this talk by Helmut Alt _{(search for "PAR is NP-complete")}. It follows that polygon packing is NP-hard, but NP-completeness has no been proven in general, as far as I am aware. One special case is proven in Packing 2×2 unit squares into grid polygons is NP-complete

A proof that packing under translation of rectangles is NP-complete is given by Richard Korf, Optimal Rectangle Packing: Initial Results. See also this talk by Helmut Alt _{(search for "PAR is NP-complete")}. This is for packing by translation only, but allowing for rotations does not change the complexity class, see this posting.

A proof that packing under translation of rectangles is NP-complete is given by Richard Korf, Optimal Rectangle Packing: Initial Results. See also this talk by Helmut Alt _{(search for "PAR is NP-complete")}.

A proof that packing under translation for rectangles is NP-complete is given in this talk by Helmut Alt _{(search for "PAR is NP-complete")} by showing that a certain integer partition problem$^*$ is efficiently reducible to the rectangle-packing problem. This result is credited to V.J. Milenkovic.

_{$^*$ Is it possible to decompose a sequence of integers into two subsequences whose sums are equal?}

A proof that packing under translation of rectangles is NP-complete is given by Richard Korf, Optimal Rectangle Packing: Initial Results. See also this talk by Helmut Alt _{(search for "PAR is NP-complete")}. This is for packing by translation only, but allowing for rotations does not change the complexity class, see this posting.