Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider a large rectangle frame, as we want to fill it with small rectangles with variable sizes. How to calculate the best match of inner objects to minimize empty spaces inside the main frame?

Alternatively, consider that the rectangle height is variable, how to re-arrange inner elements to minimize the main frame height.

An example is drawn in the following image. How to re-arrange the order (but not rotate) to fir the rectangle in the frame with minimum height (smallest possible frame).

enter image description here

share|improve this question

2 Answers 2

This is the 2D version of the bin packing problem, which Wikipedia cites as 2D packing but doesn't have a page for. Certainly it is at least as hard-just make all your rectangles have one dimension as large as the larger dimension of the frame. A search on 2D packing turns up many references.

share|improve this answer
    
It was hard to find appropriate keywords for searching. I will follow your tip to explore the problem. –  All Jun 16 '12 at 3:48

The problem is NP-hard, so only approximation algorithms are available. See the web page, Efficient algorithms for 2D rectangle packing, which compares performance on a number of such algorithms.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.