24-2 Nesting boxes

A $d$-dimensional box with dimensions $(x_1, x_2, \ldots, x_d)$ nests within another box with dimensions $(y_1, y_2, \ldots, y_d)$ if there exists a permutation $\pi$ on $\{1, 2, \ldots, d\}$ such that $x_{\pi(1)} < y_1$, $x_{\pi(2)} < y_2$, $\ldots$, $x_{\pi(d)} < y_d$.

a. Argue that the nesting relation is transitive.

b. Describe an efficient method to determine whether or not one $d$-dimensional box nests inside another.

c. Suppose that you are given a set of $n$ $d$-dimensional boxes $\{B_1, B_2, \ldots, B_n\}$. Give an efficient algorithm to find the longest sequence $\langle B_{i_1}, B_{i_2}, \ldots, B_{i_k} \rangle$ of boxes such that $B_{i_j}$ nests within $B_{i_{j + 1}}$ for $j = 1, 2, \ldots, k - 1$. Express the running time of your algorithm in terms of $n$ and $d$.

a. Consider boxes with dimensions $x = (x_1, \ldots, x_d)$, $y = (y_1, \ldots, y_d)$, and $z = (z_1, \ldots, z_d)$. Suppose there exists a permutation $\pi$ such that $x_{\pi(i)} < y_i$ for $i = 1, \ldots, d$ and there exists a permutation $\pi'$ such that $y_{\pi'(i)} < z_i$ for $i = 1, \ldots, d$, so that $x$ nests inside $y$ and $y$ nests inside $z$. Construct a permutation $\pi''$, where $\pi''(i) = \pi'(\pi(i))$. Then for $i = 1, \ldots, d$, we have $x_{\pi''(i)} = x_{\pi'(\pi(i))} < y_{\pi'(i)} < z_i$, and so $x$ nests inside $z$.

b. Sort the dimensions of each box from longest to shortest. A box $X$ with sorted dimensions $(x_1, x_2, \ldots, x_d)$ nests inside a box $Y$ with sorted dimensions $(y_1, y_2, \ldots, y_d)$ if and only if $x_i < y_i$ for $i = 1, 2, \ldots, d$. The sorting can be done in $O(d\lg d)$ time, and the test for nesting can be done in $O(d)$ time, and so the algorithm runs in $O(d\lg d)$ time. This algorithm works because a $d$-dimensional box can be oriented so that every permutation of its dimensions is possible. (Experiment with a $3$-dimensional box if you are unsure of this).

c. Construct a dag $G = (V, E)$, where each vertex $v_i$ corresponds to box $B_i$, and $(v_i, v_j) \in E$ if and only if box $B_i$ nests inside box $B_j$. Graph $G$ is indeed a dag, because nesting is transitive and antireflexive (i.e., no box nests inside itself). The time to construct the dag is $O(dn^2 + dn\lg d)$, from comparing each of the $\binom{n}{2}$ pairs of boxes after sorting the dimensions of each.

Add a supersource vertex $s$ and a supersink vertex $t$ to $G$, and add edges $(s, v_i)$ for all vertices $v_i$ with $in\text-degree$ $0$ and $(v_j, t)$ for all vertices $v_j$ with outdegree $0$. Call the resulting dag $G'$. The time to do so is $O(n)$.

Find a longest path from $s$ to $t$ in $G'$. (Section 24.2 discusses how to find a longest path in a dag.) This path corresponds to a longest sequence of nesting boxes. The time to find a longest path is $O(n^2)$, since $G'$ has $n + 2$ vertices and $O(n^2)$ edges.

Overall, this algorithm runs in $O(dn^2 + dn\lg d)$ time.