Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

In the pallet loading problem, we are asked to place a set of small identical 2-D rigid objects into a large bounding rectangle such that no two objects overlap. This problem is a special case of the cutting stock problem and is known to be NP-complete. It is NP-complete even for the special case in which the objects are identical squares [Fowler, Paterson, Tanimoto 1981].

Is pallet loading also NP-complete when the objects are non-rectangular? In particular, I am interested the case in which the objects are octagons.

share|improve this question
4  
Apparently the claims of NP-completeness of pallet loading are erroneous, according to this: cs.smith.edu/~orourke/TOPP/P55.html Do you have a more recent reference? –  Alessandro Cosentino Jan 11 '13 at 16:51
2  
@AlessandroCosentino: the entry revision of Problem 55 is rather old (2004); but in a more recent paper by Birgin, Lobato, and Morabito "An effective recursive partitioning approach for the packing of identical rectangles in a rectangle" (2007) I found: "... Apparently easy to be optimally solved, the problem is claimed to be NP-hard although it has not been proven ..." –  Marzio De Biasi Jan 11 '13 at 17:09
3  
I think it's far from trivial as packing squares into a square is fairly non-obvious; in fact it's open for many numbers of squares en.wikipedia.org/wiki/Square_packing_in_a_square. –  SamM Jan 11 '13 at 17:43
3  
@SamM: you're right (I was thinking only of orthogonal packing)! It's far from being trivial ... (see also "Packing Unit Squares in Squares: A Survey and New Results" ) –  Marzio De Biasi Jan 11 '13 at 23:25
2  
@Adam: So to be sure I understand, the inputs are the numbers $x$, $y$, and $k$, and a polygon describing the size and shape of the small object. –  usul Jan 12 '13 at 16:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.