0

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?

AIpython
  • 3
  • 2
  • 1
    The original bin packing problem is 1 dimensional. so you have a set of items, and each item has some kind of *1* dimensional value (for simplicity we act like the dimension is weight) and you have a bin which can hold some strict value of height (usually 1) and you try to split your set into the smallest number subsets so each subset could be put in a bin (so the smallest number of bins you need to put them all). more dimensions will make this question probably much harder, even so the 1 dimensional bin pack is np-hard.. more details -> https://en.wikipedia.org/wiki/Bin_packing_problem – JackRaBeat Sep 29 '22 at 10:23

1 Answers1

0

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...

Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Thank you for your answer, please could you tell me from which books or papers you have deduced this information? – AIpython Sep 29 '22 at 17:43
  • @AIpython no books just coding experience for example [here is 2D version](https://stackoverflow.com/a/21282418/2521214) with some additional constraints like no rotation. There are many variations of bin packing used in common programming tasks so once you start programming you will encounter it occasionally ... – Spektre Sep 30 '22 at 06:45