JAIST Repository
https://dspace.jaist.ac.jp/

Title

A Survey and Recent Results About Common
Developments of Two or More Boxes

Author(s)Uehara, Ryuhei

Citation

Origami^6 : proceedings of the sixthinternational meeting on origami science,
mathematics, and education: 77‑84

Issue Date

2015

Type

Book

Text version

author

URL

http://hdl.handle.net/10119/14774

RightsUehara, Ryuhei.
A Survey and Recent Results
about Common Developments of Two or More Boxes.
In Origami6: I. Mathematics, edited by Koryo
Miura, et al., 77‑84. Providence: American
Mathematical Society, 2015. ©2015 American
Mathematical Society.

Description

Japan Advanced Institute of Science and Technology

Unspecified Book Proceedings Series

A survey and recent results about common developments of two or more boxes
Ryuhei Uehara
School of Information Science, Japan Advanced Institute of Science and Technology
uehara@jaist.ac.jp

1. Introduction
Polygons that can fold into a convex polyhedron have been investigated since Lubiw and O’Rourke posed
the problem in 1996 [8]. Demaine and O’Rourke published a great book about geometric folding algorithms
that includes many results about the topic [6, Chapter 25]. In this context, there are few general results forthe relationship between polygons and polyhedra folded from the polygons. Almost only one nice result isthe following characterization of the polygons that fold into a tetramonohedron1, which is characterized bya tiling as follows (see [2, 3] for the details): A polygon P is a development of a tetramonohedron if andonly if (1) P has a p2 tiling, (2) four of the rotation centers consist in the triangular lattice formed by thetriangular faces of the tetramonohedron, (3) the four rotation centers are the lattice points, and (4) no twoof the four rotation centers belong to the same equivalent class on the tiling.
In this article, we concentrate on polygons that consist of unit squares, and orthogonal convex polyhedra,
i.e., boxes, folded from them. Biedl et al. ﬁrst ﬁnd two polygons that fold into two incongruent orthogonalboxes [5] (see also [6, Figure 25.53]). The ﬁrst one folds into two boxes of size 1 × 1 × 5 and 1 × 2 × 3, andthe second one folds into two boxes of size 1 × 1 × 8 and 1 × 2 × 5. Are these two polygons exceptional? The
answer is “no.” You can see another example in Figure 1.
We survey the series of our research on this topic. Especially, we give an aﬃrmative answer to thenatural question that asks whether there exists a polygon that folds into three diﬀerent boxes: Yes, there
exist inﬁnitely many polygons that fold into three diﬀerent boxes. So far, it is still open whether if there
exists a polygon folding to four or more distinct boxes.

Figure 1. A polygon that folds into two boxes of size 1 × 1 × 5 and 1 × 2 × 3.
c 0000 (copyright holder)

1A tetramonohedron is a tetrahedron that consists of four congruent triangular faces.
12. Preliminaries
We concentrate on orthogonal polygons that consist of unit squares. A convex orthogonal polyhedronof six rectangular faces is called a box. For a positive integer S, we denote by P (S) the set of three integers
a, b, c with 0 < a ≤ b ≤ c and ab + bc + ca = S, i.e., P (S) = {(a, b, c) | ab + bc + ca = S}. Intuitively,
2S = 2(ab + bc + ca) indicates the surface area of the box of size a × b × c. Therefore, it is necessary to satisfy|P (S)| ≥ k to have a polygon of size 2S that can fold into k incongruent orthogonal boxes. For example, thetwo known polygons in [5] correspond to P (11) = {(1, 1, 5), (1, 2, 3)} and P (17) = {(1, 1, 8), (1, 2, 5)}. Usinga simple algorithm that computes ab + bc + ca for all possible combinations of a, b, c with 1 ≤ a ≤ b ≤ c ≤ 50,
we haveP (11) ={(1, 1, 5), (1, 2, 3)}, P (15) = {(1, 1, 7), (1, 3, 3)}, P (17) = {(1, 1, 8), (1, 2, 5)},P (19) ={(1, 1, 9), (1, 3, 4)}, P (23) = {(1, 1, 11), (1, 2, 7), (1, 3, 5)}, P (27) = {(1, 1, 13), (1, 3, 6), (3, 3, 3)},
P (29) ={(1, 1, 14), (1, 2, 9), (1, 4, 5)}, P (31) = {(1, 1, 15), (1, 3, 7), (2, 3, 5)},P (32) ={(1, 2, 10), (2, 2, 7), (2, 4, 4)}, P (35) = {(1, 1, 17), (1, 2, 11), (1, 3, 8), (1, 5, 5)},
P (44) ={(1, 2, 14), (1, 4, 8), (2, 2, 10), (2, 4, 6)}, P (45) = {(1, 1, 22), (2, 5, 5), (3, 3, 6)},
P (47) ={(1, 1, 23), (1, 2, 15), (1, 3, 11), (1, 5, 7), (3, 4, 5)},P (56) ={(1, 2, 18), (2, 2, 13), (2, 3, 10), (2, 4, 8), (4, 4, 5)},
P (59) ={(1, 1, 29), (1, 2, 19), (1, 3, 14), (1, 4, 11), (1, 5, 9), (2, 5, 7)},
P (68) ={(1, 2, 22), (2, 2, 16), (2, 4, 10), (2, 6, 7), (3, 4, 8)},P (75) ={(1, 1, 37), (1, 3, 18), (3, 3, 11), (3, 4, 9), (5, 5, 5)},and so on. That is, there is no polygon that folds into two diﬀerent boxes if its surface area is less than
22 = 2 × 11 since P (i) < 2 for all 0 < i < 11. On the other hand, if we try to ﬁnd a polygon that folds into
three diﬀerent boxes, its surface should be at least 2 × 23 = 46, and in this case, three possible combinationsof height, width, and depth are 1 × 1 × 11, 1 × 2 × 7, and 1 × 3 × 5.
3. Polygons folding into Two Boxes
Even for small surface area, it is not easy to check all common developments of some boxes since they are
too huge. In 2008, we ﬁrst developed some randomized algorithms that check a part of common developments[9]. By computational experiments, we obtain over 25000 common developments of two diﬀerent boxes(including one in Figure 1, which is my most favorite one). Thousands of them can be found at http://
www.jaist.ac.jp/~uehara/etc/origami/nets/index-e.html. We give here some interesting ones among
them.

+
+

makes 1x1x8
makes 1x2x5

Figure 2. Polygon folding into two boxes of size 1 × 1 × 8 and 1 × 2 × 5, and tiling the plane.
2Tiling pattern: The discovered polygonal patterns reminded us of tiling. Indeed, there exists a simple
polygon that can fold into two boxes and it forms a tiling. The polygon in Figure 2 can fold into two boxesof size 1 × 1 × 8 and 1 × 2 × 5, and it tiles the plane.
A polygon is called a double packable solid if it tiles the plane and a polyhedron folded from the polygon
ﬁlls the space [7, Section 3.5.2]. It is easy to see that every orthogonal box ﬁlls the space. Therefore, thepolygon in Figure 2 forms two double packable solids.
As shown in Introduction, any development of a tetra(mono)hedron is characterized by the notion of p2
tiling [2, 3]. We have not yet checked if the developments of two boxes can fold into a tetra(mono)hedron.

j
1
1

+
+

makes 1x j x(4k+5)
makes 1x1x(2(j+1)(k+1)+3)

j

1

1
1

1

1

2
1
1

Copy and Paste
this area k times.

j1

Figure 3. Polygon folding into two boxes of size 1 × 1 × (2(j + 1)(k + 1) + 3) and 1 × j × (4k + 5).
Inﬁnitely many polygons: A natural question is whether or not there are inﬁnite distinct2 polygons thatcan fold into two boxes? The answer is “yes.” Some polygons in our catalogue can be generalized. From oneof them, we ﬁnd a polygon that can fold into two boxes of size 1 × 1 × (2(j + 1)(k + 1) + 3) and 1 × j × (4k + 5)
for any positive integers j and k (Figure 3).
The ﬁrst parameter j just stretches each rectangle in Figure 3 in the same rate, which has no eﬀect toconstruct two distinct boxes; two ways of folding are similar to the polygon in Figure 2. For the second
parameter k, we copy in the leftside polygon in Figure 3 and glue it to the leftmost square (with overlappingat gray areas) and repeat it k times. Then, the way of folding of the box of size 1 × 1 × (2(j + 1)(k + 1) + 3)
is essentially the same for every k; just we roll up four unit squares vertically. The way of folding of the boxof size 1 × j × (4k + 5) depends on k. We spiral up the polygon k times, and obtain vertically long rectangles.
By these ways of folding, we have two distinct boxes of diﬀerent sizes from a polygon. Therefore, there exist
an inﬁnite of distinct polygons that can fold into two boxes.
4. Polygons folding to Three Boxes
In 2011, we succeeded to enumerate all common developments of surface area 22, which is the smallest
one admitting two boxes of size 1 × 1 × 5 and 1 × 2 × 3. By an exhaustive search, we found that the numberof common developments of two boxes of size 1 × 1 × 5 and 1 × 2 × 3 is 2263 ([1]). Among resulting common
developments, there is only one exceptional development which folds into not only two boxes of size 1 × 1 × 5
and 1 × 2 × 3, but also of size 0 × 1 × 11 (Figure 4; it is also a tiling pattern). Each column of the development
has height 2 except both endpoints, which admits to fold the third box of volume 0. But this is a kind ofcheating: if you admit to have volume 0, a long ribbon can wrap doubly covered rectangles in many ways
(see [1] for further details).
In 2013, we ﬁnally found a development that folds into three diﬀerent boxes of size 2×13×58, 7×14×38,
and 7 × 8 × 56 (Figure 5). The basic idea is simple; ﬁrst we start a common development of size 1 × 1 × 8
2Precisely, distinct means gcd(a, b, c, a0 , b0 , c0 ) = 1 for two boxes of size a × b × c and a0 × b0 × c0 .
3

1x1x5

1x2x3

1x11x0Figure 4. Polygon folding into two boxes of size 1 × 1 × 5 and 1 × 2 × 3, and a box(?) of
size 0 × 1 × 11.

+

2x13x58
7x14x38+7x8x56

Figure 5. Polygon folding into three boxes of size 2 × 13 × 58, 7 × 14 × 38, and 7 × 8 × 56.

and 1 × 2 × 5. The third one is obtained by “squashing” the box of size 1 × 1 × 8 into half height of size,
roughly, 1/2 × 2 × 8. But this intuitive idea does not work in a straightforward way; a square of size 1 × 1
has perimeter 4, which is not equal to the perimeter 5 of the rectangle of size 1/2 × 2. So we use a trick tomove some area from two lid squares of size 1 × 1 to four side rectangles of size 1 × 8 in a nontrivial way
4(Figure 6). Intuitively, the zig-zag pattern can be generalized as shown in Figure 7, and we ﬁnally obtain an
inﬁnitely many polygons that fold into three diﬀerent boxes of positive volumes. See [10] for further details.
8
l1

l2 l3
l4

l2
l1

12

7
l3

A
B

10

11
15

l4
B

A

Figure 6. Squash thebox with moving a partof lid to four sides.

Figure 7. General pattern for squashing.

In
Shirakawa accidentally found two polygons that can fold into two boxes of size 1×1×7√ 2012,√ Toshihiro√
and 5 × 5 × 5. These polygons have surface area 30, which may admit to fold into another box of size
1 × 3 × 3. We have examined to enumerate all common developments of two boxes of size 1 × 1 × 5 and1 × 2 × 3, whose surface area is 22, but it takes 10 hours in 2011, and 5 hours in 2014. We use supercomputer(Cray XC30) few months with nontrivial hybrid search of the breadth-ﬁrst and depth-ﬁrst searches (see [11]for further details). As a result, we succeed to enumerate all common developments of two boxes of size
1 × 1 × 7 and 1 × 3 × 3, and the number is 1076. For these common developments,√ we√ design√ a new algorithm
that checks if an orthogonal polygon of area 30 can fold into a box of size 5 × 5 × 5. The details of
the algorithm is on preparation [12]. Among 1076 common developments√√√ of two boxes of size 1 × 1 × 7
and 1 × 3 × 3, 9 polygons can fold into the other box of√size √ 5 ×√ 5 × 5. Surprisingly, among these 9
developments, one polygon can fold into the box of size 5 × 5 × 5 in two diﬀerent ways. This amazing
polygon can be found in Figure 8.
Concluding remarks
So far, the smallest polygon folding into three boxes based on the same idea in Figure 5 requires morethan 500 unit squares. On the other hand, we have enumerated all common developments of surface area
30 which can fold into two boxes of size 1 × 1 × 7 and 1 × 3 × 3. Therefore, enumeration of all common
developments of the smallest surface area 46 which may fold into three diﬀerent boxes of size 1 × 1 × 11,
1 × 2 × 7, and 1 × 3 × 5 is the next challenging problem.
The main motivation of this research is investigation of relationship between a polygon and polyhedra
which can be folded from the polygon and vice versa. From this viewpoint, the extensions to nonorthogonal
and/or nonconvex ones are also interesting future work. For example, Araki, Horiyama, and Uehara haveinvestigated the set of polygons obtained from Johnson-Zalgaller solids by edge cutting [4]. From the set,
they extract all polygons that can fold into regular tetrahedra. However, general characterization of therelationship between a polygon and a polyhedra folded from it is still widely open.
References[1] Z. Abel, E. Demaine, M. Demaine, H. Matsui, G. Rote, and R. Uehara. Common Development of Several Diﬀerent
Orthogonal Boxes. In 23rd Canadian Conference on Computational Geometry (CCCG), pages 77–82, 2011.
[2] J. Akiyama. Tile-Makers and Semi-Tile-Makers. The Mathematical Association of Amerika, Monthly 114:602–609, AugustSeptember 2007.
[3] J. Akiyama and C. Nara. Developments of Polyhedra Using Oblique Coordinates. J. Indonesia. Math. Soc. , 13(1):99–114,
2007.
[4] Y. Araki, T. Horiyama, and R. Uehara. Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid. manuscript, 2014.
[5] T. Biedl, T. Chan, E. Demaine, M. Demaine, A. Lubiw, J. I. Munro, and J. Shallit. Notes from the University of Waterloo
Algorithmic Problem Session. September 8 1999.
[6] E. D. Demaine and J. O’Rourke. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University
Press, 2007.
5

Figure 8. Polygon √folding
three boxes of size 1 × 1 × 7, 1 × 3 × 3, and√into √The last box of size 5 × 5 × 5 can be folded in two diﬀerent ways.

√

5×

√

5×

√

5.

[7] M. Kano, M.-J. P. Ruiz, and J. Urrutia. Jin Akiyama: A Friend and His Mathematics. Graphs and Combinatorics,
23[Suppl]:1–39, 2007.
[8] A. Lubiw and J. O’Rourke. When Can a Polygon Fold to a Polytope? Technical Report Technical Report 048, Departmentof Computer Science, Smith College, 1996.
[9] J. Mitani and R. Uehara. Polygons Folding to Plural Incongruent Orthogonal Boxes. In Canadian Conference on Computational Geometry (CCCG 2008), pages 39–42, 2008.
[10] T. Shirakawa and R. Uehara. Common Developments of Three Incongruent Orthogonal Boxes. International Journal ofComputational Geometry and Applications, 23(1):65–71, 2013.
[11] D. Xu. Research on the Common Developments of Plural Cuboids. Master thesis, Japan Advanced Institute of Science andTechnology (JAIST), 2014.
[12] D. Xu, T. Shirakawa, and R. Uehara. Common Unfolding of Three Diﬀerent Boxes of Surface Area 30. manuscript, 2014.

6