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. Suppose that box \(x = (x_1, \dots, x_d)\) nests with box \(y = (y_1, \dots, y_d)\) and box \(y\) nests with box \(z = (z_1, \dots, z_d)\). Then there exist permutations \(\pi\) and \(\sigma\) such that \(x_{\pi(1)} < y_1, \dots, x_{\pi(d)} < y_d\) and \(y_{\sigma(1)} < z_1, \dots, y_{\sigma(d)} < z_d\). This implies \(x_{\pi(\sigma(1))} < z_1, \dots, x_{\pi(\sigma(d))} < z_d\), so \(x\) nests with \(z\) and the nesting relation is transitive.

b. Box \(x\) nests inside box \(y\) if and only if the increasing sequence of dimensions of \(x\) is component-wise strictly less than the increasing sequence of dimensions of \(y\). Thus, it will suffice to sort both sequences of dimensions and compare them. Sorting both length \(d\) sequences is done in \(O(d\lg d)\), and comparing their elements is done in \(O(d)\), so the total time is \(O(d\lg d)\).

c. We will create a nesting-graph \(G\) with vertices \(B_1, \dots, B_n\) as follows. For each pair of boxes \(B_i\) , \(B_j\), we decide if one nests inside the other. If \(B_i\) nests in \(B_j\), draw an arrow from \(B_i\) to \(B_j\). If \(B_j\) nests in \(B_i\), draw an arrow from \(B_j\) to \(B_i\). If neither nests, draw no arrow. To determine the arrows efficiently, after sorting each list of dimensions in \(O(nd\lg d)\) we compair all pairs of boxes using the algorithm from part (b) in \(O(n^2 d)\). By part (a), the resulted graph is acyclic, which allows us to easily find the longest chain in it in \(O(n^2)\) in a bottom-up manner. This chain is our answer. Thus, the total time is \(O(nd\max(\lg d, n))\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用