A d dimensional box with dimensions (x 1 , x 2 , ,x d ) nests within another box with dimensions (y 1 , y 2 , ,y d ) if there exists a permutation on 1, 2, ,d such that x (1) y 1 , x (2) y 2 , , x (d) y d a Argue that the nesting relation is transitive b Describe an efficient method to determine wh...

a Consider boxes with dimensions x x 1 x d yy 1 y d andzz 1 z d Suppose there exists a permutation s ...

A d-dimensional box with dimensions (x 1 , x 2 , . . . ,x d )

Question:

A d-dimensional box with dimensions (x₁, x₂, . . . ,x_d) nests within another box with dimensions (y₁, y₂, . . . ,y_d) if there exists a permutation π on {1, 2, . . . ,d} such that x_π(1) < y₁, x_π(2) < y₂, . . . , x_π(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₁, B₂, . . . ,B_n}.

Give an efficient algorithm to find the longest sequence 〈B_i₁, B_i₂, . . . ,B_i_k〉 of boxes such that B_i_j nests within B_i_j+1 for j = 1, 2, . . . ,k - 1. Express the running time of your algorithm in terms of n and d.