Dan Hussain

Comp Sci 415

September 5, 1998

Problem: Given a set of boxes with dimensions width, height, and depth, and a set of objects (also with dimensions width, height, and depth), our job is to pack the objects as efficiently as possible. If certain objects do not fit, they should to placed in a separate pile.

Simplifications:

1. All of the objects are rectangular (i.e., there are no strange shapes).

2. Assume that any empty spaces are packed with styrofoam to prevent the sliding of the objects due to gravity and other forces during shipping.

3. Assume that all objects are rigid and do not compress when weight is placed on top of them.

To get a first feel for the problem, all of the depth dimensions will be fixed to some constant c. This will allow us to simplify our three dimension problem into a simpler and more constrained two dimension one. Our problem can now be reduced to purely mathematical terms.

Reformulated Problem:

Given a set of rectangles with length and width, and another set of rectangles with length and width, arrange the second set of rectangles so that they “fit” within the first set as compactly as possible. By fit we mean that the rectangles of the second set are completely contained within the rectangles of the first set.

This is the problem we will tackle. Later, we can generalize the techniques we will learn in two dimension to apply to the original problem in three dimensions.