Title:
Enumeration of Common Developments

Speaker:
XU, Dawei (JAIST)

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 * 1 * 5 and 1 * 2 * 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 * 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 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 * 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.