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.

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.

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.

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.

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*(*n*^{2}) time on a real RAM,
and for nonconvex polygons, it runs in *O*(*n*^{2}) 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* log^{3}
*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.

- Sergei Bespamyatnikh, ``Draft:
Efficient algorithm for finding two largest empty circles,''
*Proceedings of the 15th European Workshop on Computational Geometry*, pages 37-38, 1999. - P. Bose, J. Czyzowicz, E. Kranakis, and A. Maheshwari,
``Algorithms for packing two circles in a convex polygon,''
*Proceedings of the Japan Conference on Discrete and Computational Geometry*, pages 93-103, 1998. - Prosenjit Bose, Pat Morin, and Antoine Vigneron,
``Packing
two disks into a polygonal environment,''
*Proceedings of the 7th Annual International Computing and Combinatorics Conference*, 2001. - Sung Kwon Kim, Chan-Su Shin, and Tae-Cheon Yang, ``Placing two disks in
a convex polygon,''
*Information Processing Letters*, volume 73, numbers 1-2, pages 33-39, 2000.