0

The problem is as follows: Given a 3d item and a list of 3d boxes, all rectangular cuboids, find the box with the smallest volume that can contain the given item. Only rotations by multiples of 90 degrees are allowed.

One solution is with the 3d range tree. Suppose a 3d object is defined with 3 dimensions (x, y, z) where the dimensions are sorted: x <= y <= z. Then a box (x1,y1,z1) can contain an item (x2,y2,z2) if x1 >= x2, y1 >= y2, and z1 >= z2. Thus we can use a 3d range tree to find all boxes in the range {[x2, infinity], [y2, infinity], [z2, infinity]} and return the one with the smallest volume. Is there a better or more efficient solution?

NOTE 1: related threads but not the same are 1, 2, 3.

NOTE 2: Looks like this problem can be classified under Constrained Nearest Neighbor search, see this paper.

sid
  • 1
  • 1
  • If the list of boxes is sorted by descending volume, you can stop when you get to the first box with less volume than the item. If the list of boxes is very large, you can use a binary search to get to the first box with a volume bigger than your item. – Gilbert Le Blanc Apr 01 '21 at 22:11
  • If you have only one item to fit, and you're given the boxes in a list, then you can't do better than just checking each box and remembering the smallest one that works. – Matt Timmermans Apr 01 '21 at 22:36

0 Answers0