|
|
JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >
このアイテムの引用には次の識別子を使用してください:
http://hdl.handle.net/10119/13757
|
| タイトル: | Common Developments of Three Incongruent Boxes of Area 30 |
| 著者: | Xu, Dawei
Horiyama, Takashi
Shirakawa, Toshihiro
Uehara, Ryuhei |
| キーワード: | common development
computational origami
ZDD
computational geometry |
| 発行日: | 2015-05-18 |
| 出版者: | Springer |
| 誌名: | Lecture Notes in Computer Science |
| 巻: | 9076 |
| 開始ページ: | 236 |
| 終了ページ: | 247 |
| DOI: | 10.1007/978-3-319-17142-5_21 |
| 抄録: | 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>. |
| Rights: | This is the author-created version of Springer, Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa and Ryuhei Uehara, Lecture Notes in Computer Science, 9076, 2015, 236-247. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/978-3-319-17142-5_21 |
| URI: | http://hdl.handle.net/10119/13757 |
| 資料タイプ: | author |
| 出現コレクション: | b10-1. 雑誌掲載論文 (Journal Articles)
|
このアイテムのファイル:
| ファイル |
記述 |
サイズ | 形式 |
|---|
| 21457.pdf | | 1375Kb | Adobe PDF | 見る/開く |
|
当システムに保管されているアイテムはすべて著作権により保護されています。
|
