<p>Given <span class="math-container">$n$</span> rectangles with widths <span class="math-container">$w_1,w_2,...,w_n$</span> and heights <span class="math-container">$h_1, ..., h_n$</span>. A rectangle <span class="math-container">$i$</span> fits inside <span class="math-container">$j$</span> if and only if <span class="math-container">$h_i&lt;h_j$</span> and <span class="math-container">$w_i&lt;w_j$</span>. We are interested in the maximum <span class="math-container">$k$</span> such that there exist rectangles <span class="math-container">$i_1, i_2, ..., i_k$</span> such that <span class="math-container">$i_1$</span> fits inside <span class="math-container">$i_2$</span>, <span class="math-container">$i_2$</span> fits inside <span class="math-container">$i_3$</span>, and so on until <span class="math-container">$i_k$</span>.</p>
<p>For the rectangle case, there is a pretty simple algorithm where we sort the elements in increasing order of widths, and when there are ties on widths, in descending order of height. Then find the Longest increasing subsequence (in <span class="math-container">$O(n\log n)$</span> time) in the sorted array in terms of heights and this solution corresponds to the maximum number of rectangles that can be fit inside each other.</p>
<p>My question, is there a similar approach for the <span class="math-container">$3D$</span> boxes (with length, widths, and heights) or in general in a fixed dimension <span class="math-container">$d$</span>? There is an <span class="math-container">$O(n^2)$</span> time algorithm where you build a DAG on the boxes and find the longest path, but I am interested in whether the <span class="math-container">$O(n\log n)$</span> approach generalizes in higher dimension.</p>

CC BY-SA 4.0
2021-12-25T12:39:58.597Z
If I remember correctly, that's an exercise in Cormen-Leiserson-Rivest-Stein.
Gamow
CC BY-SA 4.0
2021-12-25T20:21:16.573Z
@Gamow the 3d case or the 2d case? Happen to remember which chapter?
user3508551
<ds.algorithms><graph-algorithms>
Fastest algorithm to compute maximum number of boxes that can fit inside each other
user3508551
# Fastest algorithm to compute maximum number of boxes that can fit inside each other

(Asked by: username_0 on 2021-12-22)

Given $n$ rectangles with widths $w\_1,w\_2,...,w\_n$ and heights $h\_1, ..., h\_n$. A rectangle $i$ fits inside $j$ if and only if $h\_i and $w\_i. We are interested in the maximum $k$ such that there exist rectangles $i\_1, i\_2, ..., i\_k$ such that $i\_1$ fits inside $i\_2$, $i\_2$ fits inside $i\_3$, and so on until $i\_k$.

For the rectangle case, there is a pretty simple algorithm where we sort the elements in increasing order of widths, and when there are ties on widths, in descending order of height. Then find the Longest increasing subsequence (in $O(n\log n)$ time) in the sorted array in terms of heights and this solution corresponds to the maximum number of rectangles that can be fit inside each other.

My question, is there a similar approach for the $3D$ boxes (with length, widths, and heights) or in general in a fixed dimension $d$? There is an $O(n^2)$ time algorithm where you build a DAG on the boxes and find the longest path, but I am interested in whether the $O(n\log n)$ approach generalizes in higher dimension.

**Tags:** ds.algorithms, graph-algorithms

> **Comments:**
> **username_1**: If I remember correctly, that's an exercise in Cormen-Leiserson-Rivest-Stein.  
> **username_0**: @username_1 the 3d case or the 2d case? Happen to remember which chapter?  

---

## 0 answers

