Abstract
We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are infinitely many orthogonal polygons that folds into three boxes of different size. However, the smallest one that folds into three boxes consists of 532 unit squares. From the necessary condition, the smallest possible surface area that can fold into two boxes is 22, which admits to fold into two boxes of size \(1\times 1\times 5\) and \(1\times 2\times 3\). On the other hand, the smallest possible surface area for three different boxes is 46, which may admit to fold into three boxes of size \(1\times 1\times 11\), \(1\times 2\times 7\), and \(1\times 3\times 5\). For the area 22, it has been shown that there are 2,263 common developments of two boxes by exhaustive search. However, the area 46 is too huge for search. In this paper, we focus on the polygons of area 30, which is the second smallest area of two boxes that admits to fold into two boxes of size \(1\times 1\times 7\) and \(1\times 3\times 3\). Moreover, when we admit to fold along diagonal lines of rectangles of size \(1\times 2\), the area may admit to fold into a box of size \(\sqrt{5}\times \sqrt{5}\times \sqrt{5}\). That is, the area 30 is the smallest candidate area for folding three different boxes in this manner. We perform two algorithms. The first algorithm is based on ZDDs, zero-suppressed binary decision diagrams, and it computes in 10.2 days on a usual desktop computer. The second algorithm performs exhaustive search, however, straightforward implementation cannot be run even on a supercomputer since it causes memory overflow. Using a hybrid search of DFS and BFS, it completes its computation in 3 months on a supercomputer. As results, we obtain (1) 1,080 common developments of two boxes of size \(1\times 1\times 7\) and \(1\times 3\times 3\), and (2) 9 common developments of three boxes of size \(1\times 1\times 7\), \(1\times 3\times 3\), and \(\sqrt{5}\times \sqrt{5}\times \sqrt{5}\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Since the word “net” has several meaning, we use “development” instead of it to make clear.
- 2.
We distinguish nodes of a ZDD from vertices of a graph (or a 1-skeleton).
- 3.
We note that the maximum number of partial developments is given when \(j=24\).
References
Abel, Z., Demaine, E., Demaine, M., Matsui, H., Rote, G., Uehara, R.: Common development of several different orthogonal boxes. In: 23rd Canadian Conference on Computational Geometry (CCCG 2011), pp. 77–82 (2011)
Akiyama, J.: Tile-makers and semi-tile-makers. Math. Assoc. Amerika 114, 602–609 (2007)
Akiyama, J., Nara, C.: Developments of polyhedra using oblique coordinates. J. Indonesia. Math. Soc. 13(1), 99–114 (2007)
Araki, Y., Horiyama, T., Uehara, R.: Common unfolding of regular Tetrahedron and Johnson-Zalgaller solid. In: Rahman, M.S., Tomita, E. (eds.) WALCOM 2015. LNCS, vol. 8973, pp. 294–305. Springer, Heidelberg (2015)
Biedl, T., Chan, T., Demaine, E., Demaine, M., Lubiw, A., Munro, J.I., Shallit, J.: Notes from the University of Waterloo Algorithmic Problem Session, 8 September 1999
Demaine, E.D., O’Rourke, J.: Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press, Cambridge (2007)
Golomb, S.W.: Polyominoes. Princeton University Press, Princeton (1994)
Kane, D., Price, G.N., Demaine, E.D.: A pseudopolynomial algorithm for Alexandrov’s theorem. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 435–446. Springer, Heidelberg (2009)
Kawahara, J., Inoue, T., Iwashita, H., Minato, S.: Frontier-based search for enumerating all constrained subgraphs with compressed representation. Technical report TCS-TR-A-14-76, Division of Computer Science, Hokkaido University (2014)
Lubiw, A., O’Rourke, J.: When can a polygon fold to a polytope? Technical report 048. Department of Computer Science, Smith College (1996)
Minato, S.: Zero-suppressed bdds for set manipulation in combinatorial problems. In: 30th ACM/IEEE Design Automation Conference (DAC 1993), pp. 272–277 (1993)
Mitani, J., Uehara, R.: Polygons folding to plural incongruent orthogonal boxes. In: Canadian Conference on Computational Geometry (CCCG 2008), pp. 39–42 (2008)
Okumura, T.: Personal communication, August 2014
O’Rourke, J.: How to Fold It: The Mathematics of Linkage, Origami and Polyhedra. Cambridge University Press, Cambridge (2011)
Shirakawa, T., Horiyama, T., Uehara, R.: Construct of common development of regular tetrahedron and cube. In: 27th European Workshop on Computational Geometry (EuroCG 2011), pp. 47–50, 28–30 March 2011
Shirakawa, T., Uehara, R.: Common developments of three incongruent orthogonal boxes. Int. J. Comput. Geom. Appl. 23(1), 65–71 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Xu, D., Horiyama, T., Shirakawa, T., Uehara, R. (2015). Common Developments of Three Incongruent Boxes of Area 30. In: Jain, R., Jain, S., Stephan, F. (eds) Theory and Applications of Models of Computation. TAMC 2015. Lecture Notes in Computer Science(), vol 9076. Springer, Cham. https://doi.org/10.1007/978-3-319-17142-5_21
Download citation
DOI: https://doi.org/10.1007/978-3-319-17142-5_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-17141-8
Online ISBN: 978-3-319-17142-5
eBook Packages: Computer ScienceComputer Science (R0)