Definition: Pack a set of rectangles into a strip of width 1 to minimize the height used. Rectangles may not overlap or be rotated. Without loss of generality, the height of rectangles is at most 1. This is NP-hard.
Generalization (I am a kind of ...)
See also bin packing problem, knapsack problem, cutting stock problem.
Note: Rectangles must have widths at most 1, otherwise they wouldn't fit in the strip. If any height is greater than 1, all heights can be scaled to no more than 1.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 6 May 2005.
HTML page formatted Fri Mar 25 16:20:35 2011.
Cite this as:
Paul E. Black, "strip packing", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 6 May 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/strippacking.html