Scribd
Upload
15 views2 pages

Efficient Algorithms for Box Nesting

Uploaded by

wuyuman6
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
15 views2 pages

Efficient Algorithms for Box Nesting

Uploaded by

wuyuman6
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CS583: Analysis of Algorithms

Dr. Fei Li
Department of Computer Science
Assignment 10 — Single-Source Shortest Paths

Problem
A d-dimensional box with dimensions (x1 , x2 , . . . , xd ) nests within
another box with dimensions (y1 , y2 , . . . , yd ) if there exists a
permutation π on {1, 2, . . . , d} such that xπ(1) < y1 , xπ(2) < y2 ,
. . ., xπ(d) < yd .
1. Argue that the nesting relation is transitive.
2. Describe an efficient method to determine whether or not one
d-dimensional box nests inside another.
3. Suppose that you are given a set of n d-dimensional boxes
{B1 , B2 , . . . , Bn }. Give an efficient algorithm to find the
longest sequence < Bi1 , Bi2 , . . . , Bik > of boxes such that Bij
nests within Bij+1 for j = 1, 2, . . . , k − 1. Express the running
time of your algorithm in terms of n and d.

You might also like