Is there a faster than O(n^2) solution for Box stacking problem?

Question

The Box Stacking problem is as follows:

You are given a set of $n$ types of rectangular 3-D boxes, where the $i^{th}$ box has height $h_i$, width $w_i$ and depth $d_i$ (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.

Is there a solution faster than the $O(n^2)$ solution given here?

Answer 1

This can be solved in $\mathcal{O}(n\log^2{}n)$ by using a 2D-range query data structure to optimize the Dynamic Programming solution which has been explained in the link given in the question:

As in the link, for a box in the input with dimensions $(w_i, d_i, h_i)$, consider all rotations of the box, but maintain the property that the first dimension is always $\ge$ the second dimension. So each input box corresponds to three boxes, and consider all these $3n$ boxes, and sort them in decreasing area of the base (ie. the product of the first two dimensions).

Let this sorted sequence be $(a_1, b_1, c_1), (a_2, b_2, c_2), \ldots, (a_{3n}, b_{3n}, c_{3n})$.

Let $DP[i]$ be the maximum height that you can achieve using the first $i$ boxes in this sequence, such that the topmost box is the $i^{th}$ box. Initially $DP[i] = 0$ for all $i$. The recurrence is

$DP[i] = c_i + \max_{\substack{j < i \\ a_j > a_i \\ b_j > b_i}} DP[j]$

Now, instead of spending $\mathcal{O}(n)$ time to find this optimal $j$, we will do it faster using some data structures. Think of each box $(a_j, b_j, c_j)$ as a point $(a_j, b_j)$ in a 2D plane, which has a value $DP[j]$. Now what we want to find is the point in the rectangle $[a_i + 1, INF] \times [b_i + 1, INF]$ which has the maximum value. Note that we can ignore the constraint $j < i$ because it will be implicitly satisfied from the dimensional constraints.

For this, construct a 2D Segment Tree aka Fenwick Tree (look at the section 'Compression of 2D Segment Tree'), using $a_i$ as the values in the outer Segment Tree, and $b_i$ as the values in the inner Segment Trees. You can also use most other 2D Range Query data structures for this.

You can query for the maximum value in that rectangle in $\mathcal{O}(\log^2{}n)$ time, and once you have computed $DP[i]$, you will have to update that value in all the $\mathcal{O}(\log{}n)$ inner Segment Trees, which would take a total of $\mathcal{O}(\log^2{}n)$ time.

Hence, the problem can be solved in $\mathcal{O}(n\log^2{}n)$ time, and $\mathcal{O}(n\log{}n)$ space.