3

I have an oddly specific problem:

What is the most efficient way (resulting in the least number of cuboids) to divide a cuboid of any size (with integer dimensions) into cuboids (with integer dimensions) whose volume is 4096 or less?

For example, given an area of 234x45x322, what is the most efficient way to divide it into cuboids? Should I make as many 16^3 cuboids as possible, then binary search for the dimensions of the rest? Should I try to divide it into evenly sized rectangles?

(I'll be implementing this in Lua, but that's not overly important to the solution)

7
  • Wow, I didn't realize I gave dimensions that divided so close to 4096. @EgorSkriptunoff I need it to work with a cuboid of any size though, not just my example dimensions. Jun 5, 2016 at 17:28
  • 1
    does all cubides 'children' must have the same volume? Jun 6, 2016 at 9:01
  • @AnotherGeek No, the cuboids are allowed to be of various volumes. Jun 6, 2016 at 13:44
  • Why not use 1x1x1 cuboids? If that should not be considered a valid solution, you need to specify additional constraints that would forbid it. (Possibly related: What is "efficiency" here?) Jun 6, 2016 at 15:02
  • The efficiency is how many cuboids there are. Taking a 100x100x100 area and making it into 1,000,000,000 cuboids is not efficient. Taking a 234x45x322 area and making it into 828 cuboids (over 3.3 million cuboids) is efficient. Jun 6, 2016 at 17:33

1 Answer 1

6

Upper bound

When considering a rectangular box with width A, depth B and height C, the upper bound of the number of cuboids of maximum volume 4096 needed to fill the box is:

roundUp(A/16) × roundUp(B/16) × roundUp(C/16)

Whether you use 16×16×16 cubes to fill most of the rectangular box and smaller cuboids at the end, or divide the sides into equal lengths, you will never need more than this number of cuboids.

Using 16×16×16 cubes

Using as many 16×16×16 cubes as will fit in the rectangular box, and then using smaller cuboids for the rest of the volume, does however not guarantee the optimal result. Consider e.g. this example:

Box size: 43×38×35
Optimal solution: 14 cuboids sized 43×19×5

If you start filling the rectangular box with 8 cubes sized 16×16×16, the leftover volume consists of these parts:

slab XY: 32 x 32 x  3  (4096 x 0.75)  
slab YZ: 32 x 32 x 11  (4096 x 2.75)  
slab ZX: 32 x 32 x  6  (4096 x 1.5)  
beam X:  32 x  6 x  3  (4096 x 0.140625)  
beam Y:  32 x  3 x 11  (4096 x 0.2578125)  
beam Z:  32 x  6 x 11  (4096 x 0.515625)  
corner:   6 x  3 x 11  (4096 x 0.04833984375)  

You can combine a slab with one of its two neighbouring beams to create a bigger slab, or combine a slab with both beams and the corner to create a slab that takes up a whole side of the original cuboid, or combine the corner with one of the beams to create a longer beam, but none of these options creates a situation where you can split up the leftover volume into only 6 cuboids.

cubes, slabs, beams and corner

(image to explain terminology; not using sizes of any numerical example)

However, there are several options to split the leftover volume in 7 parts, so the overall solution is 15 instead of 14, which may be good enough as a near-optimal solution.

An algorithm based on this method would require that you consider the different ways in which the 7 leftover parts can be combined, and find which one can be split up into the fewest cuboids; this would mean calculating the optimal split of cuboids where one side is smaller than 16, which means it can be seen as a 2D problem, which is easier to solve.

It should be noted that, even if the total volume of the leftover parts is less than 4096, you will always need 3 cuboids to fill it, due to its 3D L-shape.

Equal-sized cuboids

A simple method would be to find the optimal size for a solution with equal-sized cuboids, by trying every possible combination. Since the cuboids are limited to a volume of 4096, there are only 34,720 different sizes and orientations to consider.

The code example below finds the optimal solution for the 43×38×35 example after 1634 iterations, and a solution for 999×9999×99999 after 30,183 iterations. As mentioned above, it never needs more than 34,720 iterations, which makes it quite fast, even in JavaScript.

function boxCutter(a, b, c) {
    var min = Math.ceil(a / 16) * Math.ceil(b / 16) * Math.ceil(c / 16);
    var solution = {x: 16, y: 16, z: 16, vol: 4096, num: min};
    for (var x = 1; x <= a && x <= 4096; x++) {
        for (var y = 1; y <= b && y <= 4096 / x; y++) {
            var z = Math.floor(4096 / (x * y));
            var num = Math.ceil(a / x) * Math.ceil(b / y) * Math.ceil(c / z);
            if (num < min) {
                min = num;
                solution = {x: x, y: y, z: z, vol: x * y * z, num: min};
            }
        }
    }
    return solution;
}

document.write(JSON.stringify(boxCutter(43, 38, 35)) + "<br>");
document.write(JSON.stringify(boxCutter(999, 9999, 99999)) + "<br>");

Combining the methods

If the sizes of the cuboids don't evenly divide the rectangular box, a small improvement could be obtained by running the algorithm again for the last layer of truncated cuboids, and filling this part with a different size of cuboids, similar to the second phase of the 16×16×16-cubes method.

In the example of a 999×9999×99999 rectangular box, among the 243,978,000 cuboids sized 9×5×91, there is a top layer of 222,000 cuboids whose height is truncated to 81, and a layer of 121,989 cuboids whose depth is truncated to 4. Filling one of these layers with a different size of cuboid reduces the number of cuboids by 24,198 and 24,309 respectively, or around 0.1% of the total.

3
  • Thanks for the answer. I'm going to implement this in my code :) Here it is in Lua: pastebin.com/LZTS0aSm Jun 8, 2016 at 11:38
  • @NicholasDelello A small additional improvement may be obtained by checking in which dimension the last layer of incomplete cuboids wastes most space (if any), and then running the algorithm again on this last layer. But it will probably only make a real difference for very large cuboids. (Btw, what sort of values for a, b, c and volume will you be using this for?) Jun 8, 2016 at 13:26
  • I should only be using for volumes of 4096, but a, b, and c could be quite large, as I'm using it in Minecraft for "WorldEdit"-esque selections. (Essentially, one could be selecting an entire build, and that could be spanning hundreds of blocks) As a reasonable limit, assume the largest sized selection is 1000x256x1000 (256 is the height limit). (If it's bigger than that, that'd be pretty crazy!) Jun 8, 2016 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.