Erik Demaine's Folding and Unfolding:

Wrapping Polyhedra

Given a shape, what is the most efficient way to wrap it with a piece of paper? The shape might be a flat polygon, and the goal is to fold that silhouette, or the shape might be the surface of a three-dimensional polyhedron. A wrapping is any folding of the piece of paper (without ripping or stretching) into precisely the desired shape. The folding is allowed to cover the shape with multiple layers of paper, but no paper can be strictly inside or outside the shape.

Another twist on the problem is that the paper may be colored differently on its two sides. For example, wrapping paper typically has a patterned side and a white side, and kami (common origami paper) typically has a colored side and a white side. If you are wrapping a gift, you probably want only the patterened side of the paper showing. If you are folding origami, say out of paper that is black on one side and white on the other, you might want to use the two colors to produce a particular effect of colors showing at different places in the shape. For example, it is possible to fold a single square of paper into a black-and-white checkerboard or a zebra with its stripes.


The above zebra is an origami model designed by John Montroll. It appears in his book African Animals in Origami, Dover Publications, 1991, pages 94-103.

Universality Result

The first question you might ask is, what shapes can be wrapped? More precisely, given a desired shape, can it be wrapped at all by folding a sufficiently large rectangle of paper? The answer is yes, for any connected shape composed of polygons in 3-space, each colored black or white depending on which side of the paper should show at that place. This includes flat silhouettes, two-color patterns like checkerboards or zebra, and surfaces of polyhedra.

This result was proved by Martin Demaine, Joseph Mitchell, and myself. We also give three algorithms for optimizing various metrics of the folding. For example, if we can choose the piece of paper to be a thin rectangle, we can wrap a polyhedron with arbitrarily little wastage of paper: the amount of double coverage can be reduced to as close to zero as desired. Alternatively, you can specify the locations of the seams (visible edges or creases of paper) in the wrapping, according to any decomposition of the faces into convex polygons. In particular, unless the faces have holes, there are methods for optimizing the number or total length of seams. (If the faces have holes, some of these problems become NP-complete, while others are conjectured to be NP-complete.)

For more information, you can read our paper ``Folding Flat Silhouettes and Wrapping Polyhedral Packages: New Results in Computational Origami.'' The latest version appears in Computational Geometry: Theory and Applications (2000). The paper also appears in the Proceedings of the 15th Annual ACM Symposium on Computational Geometry (1999), and in the Proceedings of the 3rd CGC Workshop on Computational Geometry (1998).

Joseph O'Rourke briefly describes this work in his ``Computational Geometry Column 36,'' which appears in International Journal of Computational Geometry and Applications, volume 9, number 6, pages 615-618; and SIGACT News, volume 30, number 3, issue 112, September 1999, pages 35-38.

Optimization

As mentioned above, given any shape and a bound on the amount of wasted paper, there is a rectangle of paper that can wrap the shape that achieves the bound on wasted paper. That is, there are wrappings whose paper usage is arbitrarily close to optimal. But this result relies on changing the initial piece of paper to be a thin rectangle. What if the shape of the paper is prescribed, e.g., to be a square? Algorithmically, what is the smallest square that can wrap a given shape?

More generally, what is the largest scaling of a given shape that can be wrapped by a given piece of paper? The decision version of this optimization problem is, given a desired shape and a piece of paper, can the shape be wrapped by the piece of paper?

Most of these problems remain open. Several specific instances have been explored, with conjectured optimal solutions, in Serhiy Grabarchuk's Wrapping Puzzles. One version that has been explored more rigorously is wrapping a cube with various rectangles. Another such variation is disk hiding. Both of these topics are described below.

Wrapping a Cube

Given a rectangular piece of paper with particular dimensions, what is the largest cube that can be wrapped? For thin rectangles, arbitrarily large cubes can be wrapped, but what is the exact trade-off between thickness of the rectangle and size of the cube? This intriguingly simple-sounding problem remains unsolved. Some versions and solutions (not necessarily optimal) are described by Scott Kim in his Bogglers column, Discover, February 2001, page 86.

The only instance of wrapping of which I know that has been solved is wrapping a cube with a square. The solution has been conjectured for a while. For example, John Conway showed it to me at a conference in 2000. A picture of the solution is shown on MathPuzzle and on Juergen Koeller's Origami Cube page. That this solution is optimal was finally proved by Michael L. Catalano-Johnson and Daniel Loeb in ``Problem 10716: A cubical gift,'' American Mathematical Monthly, volume 108, number 1, January 2001, pages 81-82 (posed in volume 106, 1999, page 167).

Two interesting variations on the cube-wrapping problem are posed by Henry Larson, in ``Problem 628: A Cube Pattern Puzzle,'' Journal of Recreational Mathematics, volume 10, number 2, 1978, page 129. A rectangular 9-by-12 piece of paper can be cut into either a union of six squares (hexomino) or into an arbitrary connected polygon, and then that cut-out piece must be folded into the largest cube possible. Solutions to these puzzles appear in Journal of Recreational Mathematics, volume 11, number 3, 1978, pages 219-223. The first puzzle was solved by Kenry A. Kierstead, and can be solved by enumeration; the resulting side length of the cube is around 3.053. The second puzzle was solved by Racine Carré with assistance from the poser: there is a way to wrap a cube with surface area arbitrarily close to the area of the rectangle, based on cutting and folding it into a thin strip. This method works for any rectangle.

Disk Hiding

A related problem to optimal wrapping is the following. Given a polygonal piece of paper, what is the largest disk that can be hidden? That is, the disk must be covered on both sides, but the folding does not have to perfectly wrap the disk (it can have excess paper outside the disk, as is necessary). The idea is that this problem has few parameters (just the shape of the piece of paper), but may give insight into optimal wrappings of convex polygons.

The initial paper on this problem is ``Hiding Disks in Folded Polygons,'' by Therese Biedl, Martin Demaine, Anna Lubiw, Godfried Toussaint, and myself, which appears in the Proceedings of the 10th Canadian Conference on Computational Geometry. We distinguish wrappings by how many simple folds they require. (A simple fold is a fold along a single line.) For folding a square with 2, 3, 4, or more folds, we give conjectured optimal wrappings of the largest disk, which remain open. In the following figure, we give the best known ``nontrivial'' foldings with k folds, nontrivial in the sense that they do not approximate the solution for j folds for j < k. Only the 1-fold case is known to be optimal. The conjecture is that 5 folds do not help.

The most interesting general result is when just a single fold along a line is allowed. What is the largest disk that can be hidden by a single fold of a given polygonal piece of paper? If we unfold the hiding and examine the top and bottom copies of the disk, we discover that any such hiding determines two disjoint equal-radius disks packed in the polygonal piece of paper, and vice versa:

Thus, the problem becomes this: what is the largest pair of nonoverlapping equal-radius disks that can be packed into a given polygon? We proved that this question can be answered in polynomial time. Specifically, for convex polygons, our algorithm runs in O(n2) time on a real RAM, and for nonconvex polygons, it runs in O(n2) time multiplied by the number of bits desired in the answer. (This last part is required for solving degree-8 polynomial (monomial) equations.)

Recently, this problem has been explored in several followup papers. The references are given below. For convex polygons, Bose, Czyzowicz, Kranakis, and Maheshwari (1998) developed a linear-time algorithm, and Kim and Shin (2000) developed an O(n log n)-time algorithm. For simple polygons, Bespamyatnikh (1999) developed an O(n log3 n)-time algorithm using parametric search. For general polygons with holes, Bose, Morin, and Vigneron (2001) have developed a randomized O(n log n)-time algorithm.

Erin McLeish prepared an excellent webpage describing these results and algorithms for disk packing, including a Java applet.

Last updated November 28, 2010 by Erik Demaine.