<p>If I understand David Eppstein's<sup>1 </sup> <a href="https://arxiv.org/abs/0908.3916" rel="nofollow noreferrer">explanation (see section 3)</a> 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?)</p>

<p>In your example, there is only one such diagonal:</p>

<pre><code> ________
|        |
|_x....x_|
  |____|
</code></pre>

<p>The two <code>x</code>s represent connected concave vertices. The maximal independent set of edges here contains only one edge, splitting the polygon in two.</p>

<p>Here's another with only one axis-parallel edge connecting two concave vertices, <code>x</code> and <code>x</code>. This polygon, though, also has two concave vertices, <code>a</code> and <code>b</code>, 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):</p>

<pre><code> ____________
|            |
|            |x
|            . |
|            . |a
|___         .   |
   b|        .   |
    |        .___|
    |________|x
</code></pre>

<p>results in 4 rectangles:</p>

<pre><code> ____________
|            |
|            |x
|            . |
|            ..|a
|___..........   |
   b|        .   |
    |        .___|
    |________|x
</code></pre>

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

<pre><code> ____________
|            |
|            |x_
|            .  |
|            .  |
|___ . . . .z. .|y
   y|        .    |
    |        .____|
    |________|x
</code></pre>

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

<pre><code>(y,z) (z,y) (x,z) (z,x)
</code></pre>

<p>yielding 4 rectangles as a solution.</p>

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

<p><sub>1. Graph-Theoretic Solutions to Computational Geometry Problems, David Eppstein (Submitted on 26 Aug 2009)</sub></p>
Any algorithm to fill a space with smallest number of boxes
<p>Let 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.</p>

<p>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".</p>

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

<pre><code>+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   | A | B | C | D |   |
+---+---+---+---+---+---+
|   | E | F | G | H |   |
+---+---+---+---+---+---+
|   |   | K | L |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
</code></pre>

<p>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 :</p>

<pre><code>+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   | A | B | B | C |   |
+---+---+---+---+---+---+
|   | A | B | B | C |   |
+---+---+---+---+---+---+
|   |   | B | B |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
</code></pre>

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

<pre><code>+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   | A | A | A | A |   |
+---+---+---+---+---+---+
|   | A | A | A | A |   |
+---+---+---+---+---+---+
|   |   | B | B |   |   |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
</code></pre>

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

<p>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 !</p>

<p>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. Thanks !!</p>