<p>If you model a box as a point <span class="math-container">$(b_1,b_2, \ldots, b_d)$</span>, and you define the dominance relationship <span class="math-container">$p \prec q$</span>  <span class="math-container">$\iff$</span> <span class="math-container">$p_i &lt; q_i$</span>, for all <span class="math-container">$i$</span>, then you are looking for the longest chain in this partial order. In <span class="math-container">$d$</span> dimensions this problem can be solved in <span class="math-container">$O(n \log^{d} n)$</span> times, I believe.</p>
<p>I would sketch a somewhat inferior solution, because it is late.</p>
<p>To see how to do it, consider the two dimensional case. For a point <span class="math-container">$p$</span>, let <span class="math-container">$||p||_1 = |x(p)| + |y(p)|$</span>. Consider the input points, <span class="math-container">$p_1, \ldots, p_n$</span>, and observe that <span class="math-container">$p_i \prec p_j$</span> only if <span class="math-container">$||p_i||_1 &lt; ||p_j||_1$</span>. As such, sort the points by their <span class="math-container">$L_1$</span> norm, in increasing ordering, and let <span class="math-container">$p_1,\ldots, p_i$</span> be the points handled so far, where for each <span class="math-container">$p_j$</span>, <span class="math-container">$j=1,\ldots, i$</span>, we computed <span class="math-container">$\ell(p_j)$</span> -- the length of the longest path in the relation that ends at <span class="math-container">$p_j$</span>. We add the extra dimension <span class="math-container">$\ell(p_j)$</span> to the point <span class="math-container">$p_j$</span>, so that this is now its third coordinate.</p>
<p>Now, given a new point <span class="math-container">$p_{i+1}$</span>, we need to compute the highest point (in the third dimension) that it dominates (in the first two dimensions) -- this is an open quadrant question, and can be solved in <span class="math-container">$O( \log^{O(1)} n)$</span> time using orthogonal range searching techniques. Assume you get the point <span class="math-container">$p_k$</span> as returned by the query -- we have that <span class="math-container">$\ell_{i+1} = \ell(p_{i+1}) = \ell(p_k)+1$</span>. We need to insert this new point <span class="math-container">$(p_{i+1}, \ell_{i+1})$</span> in the the orthogonal range searching data-structure.</p>
<p>Thus, you can handle each point in <span class="math-container">$O(\log^{O(1)} n)$</span> time which readily implies that you can compute the longest chain in <span class="math-container">$O( n\log^{O(1)} n)$</span> time. Being more careful about the details, the running time can be improved to <span class="math-container">$O(n \log n)$</span> in two dimensions.</p>
<p>I have a paper on a related problem here:</p>
<p><a href="https://arxiv.org/abs/1910.07586" rel="nofollow noreferrer">https://arxiv.org/abs/1910.07586</a></p>
<p>I think a solution for your problem should be readily implied by some previous work.</p>
<p>More maybe later...</p>

CC BY-SA 4.0
2020-10-20T17:59:02.630Z
It would be interesting to abstract out the general principles in these problems. Basically we have a  longest path problem in a DAG where the DAG vertices correspond to objects and edges are implicitly defined and easy to compute. One would like to avoid computing the full DAG and still do longest path computation. So a proxy ordering is defined and data structures are used to speed up the computation.
Chandra Chekuri
CC BY-SA 4.0
2020-10-20T04:38:26.473Z
2020-10-20T04:38:26.473Z
Sariel Har-Peled
<p>You are given <span class="math-container">$n$</span> boxes and want to stack them to make a tallest possible tower, but you can only stack a box on top of another if the base is smaller in both dimensions.  This is a classic dynamic programming problem, and yet I can't easily find answers online to natural questions:</p>
<ol>
<li>If the boxes cannot be rotated, what is the complexity of this problem?  A standard dynamic programming algorithm gives <span class="math-container">$O(n^2)$</span>.  Can you do <span class="math-container">$O(n \log n)$</span>?  Any conditional lower bounds?</li>
<li>If the boxes can be rotated, what is the complexity?  Note that I do not have <span class="math-container">$n$</span> types of boxes and infinite instances of each type, I have <span class="math-container">$n$</span> boxes.</li>
<li>What is the complexity in higher dimensions?</li>
<li>What is the complexity if the dimensions are integers from <span class="math-container">$1$</span> to <span class="math-container">$k$</span>?</li>
</ol>

<dynamic-programming>
Box stacking problem, and variants
Manu
# Box stacking problem, and variants

(Asked by: username_0 on 2020-10-19)

You are given $n$ boxes and want to stack them to make a tallest possible tower, but you can only stack a box on top of another if the base is smaller in both dimensions. This is a classic dynamic programming problem, and yet I can't easily find answers online to natural questions:

1. If the boxes cannot be rotated, what is the complexity of this problem? A standard dynamic programming algorithm gives $O(n^2)$. Can you do $O(n \log n)$? Any conditional lower bounds?
2. If the boxes can be rotated, what is the complexity? Note that I do not have $n$ types of boxes and infinite instances of each type, I have $n$ boxes.
3. What is the complexity in higher dimensions?
4. What is the complexity if the dimensions are integers from $1$ to $k$?

**Tags:** dynamic-programming

---

## 1 answers

### Answer by username_1 on 2020-10-20. Score: 2

If you model a box as a point $(b\_1,b\_2, \ldots, b\_d)$, and you define the dominance relationship $p \prec q$ $\iff$ $p\_i < q\_i$, for all $i$, then you are looking for the longest chain in this partial order. In $d$ dimensions this problem can be solved in $O(n \log^{d} n)$ times, I believe.

I would sketch a somewhat inferior solution, because it is late.

To see how to do it, consider the two dimensional case. For a point $p$, let $||p||\_1 = |x(p)| + |y(p)|$. Consider the input points, $p\_1, \ldots, p\_n$, and observe that $p\_i \prec p\_j$ only if $||p\_i||\_1 < ||p\_j||\_1$. As such, sort the points by their $L\_1$ norm, in increasing ordering, and let $p\_1,\ldots, p\_i$ be the points handled so far, where for each $p\_j$, $j=1,\ldots, i$, we computed $\ell(p\_j)$ -- the length of the longest path in the relation that ends at $p\_j$. We add the extra dimension $\ell(p\_j)$ to the point $p\_j$, so that this is now its third coordinate.

Now, given a new point $p\_{i+1}$, we need to compute the highest point (in the third dimension) that it dominates (in the first two dimensions) -- this is an open quadrant question, and can be solved in $O( \log^{O(1)} n)$ time using orthogonal range searching techniques. Assume you get the point $p\_k$ as returned by the query -- we have that $\ell\_{i+1} = \ell(p\_{i+1}) = \ell(p\_k)+1$. We need to insert this new point $(p\_{i+1}, \ell\_{i+1})$ in the the orthogonal range searching data-structure.

Thus, you can handle each point in $O(\log^{O(1)} n)$ time which readily implies that you can compute the longest chain in $O( n\log^{O(1)} n)$ time. Being more careful about the details, the running time can be improved to $O(n \log n)$ in two dimensions.

I have a paper on a related problem here:

<https://arxiv.org/abs/1910.07586>

I think a solution for your problem should be readily implied by some previous work.

More maybe later...

> **Comments:**
> **username_2**: It would be interesting to abstract out the general principles in these problems. Basically we have a  longest path problem in a DAG where the DAG vertices correspond to objects and edges are implicitly defined and easy to compute. One would like to avoid computing the full DAG and still do longest path computation. So a proxy ordering is defined and data structures are used to speed up the computation.  

---

