Any algorithm to fill a space with smallest number of boxes

Question

I have a 3D grid, just like a checkerboard, with an extra dimension. Now let's say that I have a certain amount of cubes into that grid, each cube occupying 1x1x1 cells. Let's say that each of these cubes is an item.

What I would like to do is replace/combine these cubes into larger boxes occupying any number of cells on the X, Y and Z axes, so that the resulting number of boxes is as small as possible while preserving the overall "appearance".

It's probably unclear so I'll give a 2D example. Say I have a 2D grid containing several squares occupying 1x1 cells. A letter represents the cells occupied by a given item, each item having a different letter from the other ones. In the first example we have 10 different items, each of them occupying 1x1x1 cells.

+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   | A | B | C | D |   |
+---+---+---+---+---+---+
|   | E | F | G | H |   |
+---+---+---+---+---+---+
|   |   | K | L |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+

That's my input data. I could now optimize it, i.e reduce the number of items while still occupying the same cells, by multiple possible ways, one of which could be :

+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   | A | B | B | C |   |
+---+---+---+---+---+---+
|   | A | B | B | C |   |
+---+---+---+---+---+---+
|   |   | B | B |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+

Here, instead of 10 items, I only have 3 (i.e A, B and C). However it can be optimized even more :

+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   | A | A | A | A |   |
+---+---+---+---+---+---+
|   | A | A | A | A |   |
+---+---+---+---+---+---+
|   |   | B | B |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+

Here I only have two items, A and B. This is as optimized as this can be.

What I am looking for is an algorithm capable of finding the best item sizes and arrangement, or at least a reasonably good one, so that I have as few items as possible while occupying the same cells, and in 3D !

Is there such an algorithm ? I'm sure there are some domains where that kind of algorithm would be useful, and I need it for a video game.

Answer 1

If I understand David Eppstein's¹ explanation (see section 3) then a solution can be found in a maximal independent set in the bipartite intersection graph of axis-aligned diagonals connecting one concave vertex to another. (This would be 2d. I'm not sure about 3d, although perhaps it involves evaluating hyperplanes instead of lines?)

In your example, there is only one such diagonal:

 ________
|        |
|_x....x_|
  |____|

The two xs represent connected concave vertices. The maximal independent set of edges here contains only one edge, splitting the polygon in two.

Here's another with only one axis-parallel edge connecting two concave vertices, x and x. This polygon, though, also has two concave vertices, a and b, that do not have an opposite, axis-parallel match. In that case, it seems to me, each concave vertex without a partner would split the polygon it's on in two (either vertically or horizontally):

 ____________
|            |
|            |x
|            . |
|            . |a
|___         .   |
   b|        .   |
    |        .___|
    |________|x

results in 4 rectangles:

 ____________
|            |
|            |x
|            . |
|            ..|a
|___..........   |
   b|        .   |
    |        .___|
    |________|x

Here's one with two intersecting axis-parallel diagonals, each connecting two concave vertices, (x,x) and (y,y):

 ____________
|            |
|            |x_
|            .  |
|            .  |
|___ . . . .z. .|y
   y|        .    |
    |        .____|
    |________|x

In this case, as I understand, the intersection graph again contains only one independent set:

(y,z) (z,y) (x,z) (z,x)

yielding 4 rectangles as a solution.

Since I'm not completely sure how the "intersection graph" in the paper is defined, I would welcome any clarifying comments.

_{1. Graph-Theoretic Solutions to Computational Geometry Problems, David Eppstein (Submitted on 26 Aug 2009)}

Answer 2

Perhaps a simpler algorithm is possible, but a set partition should suffice.

Min       x1 + x2 + x3 + ... //where x1 is 1 if the 1th partition is chosen, 0 otherwise
such that x1 +    + x3 = 1// if 1st and 3rd partition contain 1st item
               x2 + x3 = 1//if 2nd and 3rd partition contain 2nd item and so on.

          x1, x2, x3,... are binary

You have 1 constraint for each item. Each constraint stipulates that each item can be part of exactly one box. The objective minimizes the total number of boxes.

This is an NP Hard integer programming however.

The number of variables in this problem could be exponential. You need to have an efficient way of enumerating them -- that is figuring out when a contiguous box can be found that is capable of including all points in it. It is here that you have to take into account information such as whether the grid is 2d or 3d, how you define a contiguous "box", etc.

Such problems are usually solved by column-generation, where these columns of the integer program are dynamically generated on the fly.