Wraptimisation 2: The Wrappening

It’s been that time of year again, where I am forced to face my one and only weakness: wrapping presents. Rather than confront my failings, I’ve once again turned to my old friends: maths, computers, and bad puns.

This post is about wrapping presents as efficiently as possible, using the minimum amount of wrapping paper.

The last time I approached this, I was interested in Lagrange multipliers rather than geometry, so the wrapping process was simplified. Additionally, while the volume of the present was fixed, the surface area was allowed to change, and we minimised the area of the wrapping paper required.

These two inadequacies were pointed out in the comments, so this time I’ve sought a more general solution, mathematical simplicity be damned.

Problem

The present is a cuboid of side lengths $a, b, c$ with $a > b > c$
The wrapping paper is a rectangle of side lengths $w, h$
The wrapping process is to place the present on the centre of the wrapping paper on it’s largest face (of area $ab$ ), optionally rotate the paper by some angle $\theta$ , then fold the paper up around the present onto the top face
The paper must cover all of the surface area of the present
The efficiency of the wrap $\epsilon < 1$ is defined as the ratio of the surface area of the present to the area of the paper:

$\displaystyle{\epsilon = \frac{2(a\cdot b + a \cdot c + b \cdot c)}{w \cdot h}}$

Our aim is to find a $w, h, \theta$ which covers the present with maximum efficiency.

To visualise this wrapping process, let’s look at a generic case. Below, on the left you’ll see the wrapping paper in blue, the box in gray, and the covered areas of the present highlighted in red.

On the left the present has been unfolded such that the base is in the centre, and 4 replicas of the top are indicated in dotted lines

The enlarged view to the right shows how the top looks once the folded parts are included from the four separate sides. In this case, we see that the coverage is below 1, as we are not covering parts of the top or left and right sides.

To rectify this, we could increase the size of the paper to make sure that the top is covered, at the expense of some overlap and wasted paper:

As we shall see later on, an efficiency of 0.59 is not particularly good…

Wrapping methods

To get our heads in the game, let’s quickly enumerate some possible wrapping methods.

Tall

This strategy is to make the wrapping paper just wide enough to cover the sides, and tall enough to cover half of the top:

Wide

Similarly to the above, but with the long edge width-ways:

Diagonal

Now with the paper rotated by 45 degrees, just touching the corners of the sides:

Oblique

With the paper rotated such that the overlap on the lid is minimised:

In this particular case, we can see that the diagonal approach is the most efficient. The obvious questions though, are

Is the 45 degree angle special?
Does the optimal angle vary with present dimensions?
Are there particularly sub-optimal present shapes?

Let’s have a look at answering some of these.

Finding optimal wrappings

For a given present, an optimal wrapping (as defined above) is a 3-dimensional optimisation problem. I had some trouble just plugging this in to the standard scipy solvers, but ended on an approach of

A coarse grid search over $w,h$ , at each point running a 1D optimisation pass on $\theta$
A fine 3D optimisation with the best coarse search results as the starting position

The coarse grid search is also useful for getting a feel for the efficiency landscape. Below are plotted the optimal $\theta$ and $\epsilon$ as a function of $w,h$ for the present above.

The black dotted region is that area with full coverage, the blue dot represents the highest efficiency found in the grid search, and the orange star the finessed 3D optimisation fit.

As expected, optimal wrapping occurs on the edge of the valid region with the smallest paper size. It is also clear that making the wrapping paper too small in either dimension makes it impossible to fully wrap the present, constraining the search space.

With an optimisation procedure in hand, let’s see what optimal wrappings look like as a function of present shape. Because the efficiency as we’ve defined it is related to the present surface area, the space of all efficiencies is two-dimensional. Given that

$\displaystyle{a > b > c}$

define

$\displaystyle{b = \alpha a, \quad c = \beta b = \alpha\beta a, \quad \alpha \leq 1, \quad \beta \leq 1}$

then the space of available presents looks like:

i.e. $\alpha = \beta = 1$ represents cube, and $\alpha, \beta \rightarrow 0$ makes the present increasingly flat.

Some number-crunching later, we have our results as a function of $\alpha, \beta$ :

This is interesting – bar a few numerical glitches, it is clear that most presents should be wrapped using the Diagonal strategy at an angle of $45^{\circ}$ . There is also a pretty sharp cutoff for smaller $\alpha$ at which point the optimal angle drops to $\approx 30^{\circ}$ , and then again down to zero.

There are also two particularly sub-optimal present shapes – one for a perfect cube, and one around $\alpha \approx 0.25, \beta = 1$ . To dig into these surprises a little more, we have to go back to some algebra.

Analytical results

There’s a reason I picked the 4 wrapping strategies defined above – they were the ones most often produced by the optimisation procedure, and also analytically tractable.

You might want to have a go at deriving these yourselves, but the efficiencies for these strategies are:

Tall

$\displaystyle{\epsilon = \frac{1 + \alpha\beta + \beta}{(1 + \beta)(1 + 2\alpha\beta)}}$

Wide

$\displaystyle{\epsilon = \frac{1 + \alpha\beta + \beta}{(1+\beta)(1+2\alpha\beta)}}$

Diagonal

This is always guaranteed to cover the whole present for $\alpha, \beta \leq 1$ , and produces a square result for the paper.

$\displaystyle{\epsilon = \frac{4\alpha(1 + \alpha\beta + \beta)}{(1 + \alpha + 2\alpha\beta)^2}}$

Oblique

This one is slightly trickier – the angle to rotate is given by $\tan(\theta) = \alpha$ and the paper has to be extended slightly to make sure the whole present is covered.

$\displaystyle{\epsilon = \frac{(1 + \alpha^2)(1 + \alpha\beta + \beta)}{(1 + \beta)(1 + \alpha^2 + 2\alpha\beta)}}$

These efficiencies look like:

The ‘wide’ strategy never works, as might be expected given the shapes of these presents. The ‘tall’ and ‘oblique’ strategies are very similar for small $\alpha$ , which makes sense as for the ‘oblique’ strategy the rotation angle goes to zero there.

If you take the maximum at each point, then the winning strategies turn out to be the ‘diagonal’ and ‘oblique’ strategies:

The line dividing these two strategies can be calculated to be

$\displaystyle{\beta = \frac{\sqrt{2\alpha^5 + \alpha^4 + \alpha^2} - \alpha^2 - \alpha^2}{2\alpha^2(1 + \alpha)}}$

which means that any present lying along this line will be the most difficult to wrap efficiently. The worst one is in fact the one illustrated at the beginning of this post, and is given by

$\beta = 1$

$\displaystyle{\alpha = \frac{1}{27}\left(-7 + \left(22\left(47-27\sqrt{3}\right)\right)^{1/3} + \left(22\left(47+27\sqrt{3}\right)\right)^{1/3}\right) \approx 0.27}$

with an efficiency of $\epsilon \approx 0.752$ using the ‘diagonal’ or ‘oblique’ strategies.

The worst present of all though? The humble cube, with a simple-to-calculate efficiency of $\epsilon = 0.75$ .

While these results are fun to produce and more generic than last time, there are still many more cases to consider. For example, at each ‘fold’ of the paper there may be multiple edges to consider. Should one edge be preferred? What about folding around the present multiple times? What about minimising the number of folds?

With this knowledge in hand, I’ll be sure to smash the present wrapping game next year. Happy holidays!

One thought on “Wraptimisation 2: The Wrappening”

Pingback: How to wrap packages with maximum paper efficiency #Math #ProblemSolving « Adafruit Industries – Makers, hackers, artists, designers and engineers!

Almost looks like work

Wraptimisation 2: The Wrappening

Problem

Wrapping methods

Finding optimal wrappings

Analytical results

One thought on “Wraptimisation 2: The Wrappening”

Leave a Reply Cancel reply

Problem

Wrapping methods

Finding optimal wrappings

Analytical results

Share this:

Like this:

Related

One thought on “Wraptimisation 2: The Wrappening”

Leave a Reply Cancel reply