Common Developments of Three Incongruent Boxes of Area 30

• Xu, Dawei

• Horiyama, Takashi

• Shirakawa, Toshihiro

• Uehara, Ryuhei

Abstract

We investigate common developments that can fold into plural incongruent orthogonal boxes. Recently, it was shown that there are inｆinitely 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×1×5 and 1×2×3. On the other hand, the smallest possible surface area for three different boxes is 46, which may admit tofold into three boxes of size 1×1×11, 1×2×7, and 1×3×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×1×7 and 1×3×3. Moreover, when we admit to fold along diagonal lines of rectangles of size 1×2, the area may admit to fold into a box of size √<5>×√<5>×√<5>. That is, the area 30 is the smallest candidate area for folding three different boxes in this manner. We perform twoalgorithms. 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 supercomputersince 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×1×7 and 1×3×3, and (2) 9 common developments of three boxes of size 1×1×7, 1×3×3, and √<5>× √<5>×√<5>.

Theory and Applications of Models of Computation, 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/13757

Journal

• Lecture Notes in Computer Science

  Lecture Notes in Computer Science 9076 236-247, 2015-05-18

  Springer

Keywords

• common development
• computational origami
• ZDD
• computational geometry

Details

• CRID: 1050845762468621184
• NII Article ID: 120005850316
• ISSN: 03029743
• Web Site: http://hdl.handle.net/10119/13757
• Text Lang: en
• Article Type: journal article
• Data Source:
  • IRDB
  • CiNii Articles