Associated Topics || Dr. Math Home || Search Dr. Math

### Maximizing the Number of Rectangles

```
Date: 10/26/2000 at 03:32:59
From: Bryan Santiago
Subject: Maximizing paper use

Hi! I have been trying to devise a method of cutting up a sheet of
rectangular paper into smaller rectangular pieces of equal sizes. Say
I have a sheet that is L x W big and I need pieces that are A x B
small. How many pieces can I get?

The system I have now uses this method (L > W, A > B). It divides the
paper into a grid of pieces of dimensions A x B. If any of the paper
is left over, it divides the rest into a grid of B x A pieces. Then it
adds up all the pieces.

x1 = L/A
y1 = W/B
x2 = L-A*x1/W
y2 = W/A
outA = (x1*y1) + (x2*y2)

Sometimes this is not efficient, so I repeat the process with A and B
switched.

x3 = L/B
y3 = W/A
x4 = W-B*y3/L
y4 = W/B
outB = (x3*y3) + (x4*y4)

I use whichever is larger, outA or outB. Though this works most of the
time, I have found exceptions.

For example, say I have a sheet of paper that is 13x8 and I need
pieces that are 3x2.

outA = (4*4) + (0*2) = 16
outB = (6*2) + (0*4) = 12

It seems that 16 is the maximum, but I have discovered that you can
rearrange the pieces in order to get 17. I have no idea how to compute
for this. I need the information for a Java applet I am working on
that gives you the maximum number of pieces you can get and at the
same time draws the orientation of the pieces.
```

```
Date: 10/26/2000 at 17:10:26
From: Doctor Rob
Subject: Re: Maximizing paper use

Thanks for writing to Ask Dr. Math, Bryan.

The problem you are faced with is, in general, a very difficult one.
It is a two-dimensional version of a famous one-dimensional problem
called the Knapsack Problem. The Knapsack Problem has been proved to
be in complexity class NP-complete. That means that the hardest
Knapsack Problems are believed to take exponential time to solve. Of
course, there are easy instances (fitting 1x1 rectangles in a 8x13
rectangle is pretty easy).

There is an upper bound that you can easily compute. Divide the area
of the large rectangle by the area of the small rectangle. The number
of small ones cannot exceed this bound. 13*8/(3*2) = 104/6 = 17.333,
so one cannot fit more than 17 3x2 rectangles into a 13x8 rectangle.
This tells you nothing about the actual layout, of course.

An additional complicating factor is that occasionally it is
advantageous to put the small rectangles with their sides NOT parallel
to the sides of the large rectangle. For a 13x8 rectangle, a 14x1
rectangle won't fit with sides parallel, but it will fit diagonally
(actually, two will fit).

Probably there is a theorem that says that if the large rectangle's
dimensions are large enough with respect to the small rectangle's
dimensions, then the maximum number allowable by the area bound will
be possible to find with all sides parallel. The way to show that such
a theorem is true is to cut the large rectangle up into smaller
rectangular pieces that can be cut up into small rectangles with no
waste, except for one remaining piece whose area is smaller than that
of the small rectangles.

In the case you cite, you can cut off a 9x8 rectangle from your 13x8
rectangle. That can be cut into small rectangles with no waste
(3*3 = 9, 4*2 = 8, so 3*4 = 12 small rectangles aligned horizontally
will do it). That leaves a 4x8 rectangle. From this you can cut off a
4x6 piece that can be formed from four small rectangles vertically
aligned, leaving a 4x2 piece. From this piece you can cut off a 3x2
piece which is one small rectangle horizontally aligned, leaving a 1x2
piece that is wasted. That gives you the 17 small rectangles.

The trick is to find the way to cut the large rectangle into these
efficient pieces.

Sorry, but this seems very hard to do algorithmically.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Discrete Math
College Euclidean Geometry

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search