What is the difference between 1D-, 2D and 3D Bin packing problem?

Question

What does increasing the dimensions produce? Every box or object will always have 3 dimensions: length, width and height in addition to its weight. So what do the dimensions refer to?

Answer 1

No expert on the matter so read with prejudice. The dimensionality stands for the dimensionality of packed items and space we work with. Bin packing itself is about 2 core problems:

1. place as many items into confined space (bin)
2. divide items along more bins so they have as least waste space as possible

While the #2 is more or less the same for any dimensionality the #1 gets significantly harder as for each item we need to fit:

1. 1D x
2. 2D x,y,axy
3. 3D x,y,z,axy,ayz,azx
4. 4D x,y,z,w,axy,axz,axw,ayz,ayw,azw

where x,y,z,... are position coordinates and axy,ayz,azx,... are rotation angles (along major planes)

so for n items and mp possible positions and ma possible angles and single bin we have:

1D: O(n.mp)
2D: O(n.mp^2.ma)
3D: O(n.mp^3.ma^3)
4D: O(n.mp^4.ma^6)

as you can see its growing fast with dimensionality and even 2D is very hard. To improve speed heuristics (like precomputed placement patterns,align to some major side of object, limiting angular positions etc...) is usually used and or different approaches like field or gravity simulation based...