.svg){kind=logo}
VALIDITY OF BOUNDARY ORDERS IN FLAT-FOLDING 1-DIAGONAL GRID PATTERNS
Keywords:
map folding problem, valid boundary orders, 1-diagonal grid patternsDOI:
https://doi.org/10.17654/0974165825040Abstract
In this paper, we investigate a particular variation of the valid order problem, which is derived from the map folding problem. Our focus is on folding a grid pattern augmented with half of the diagonal creases to form a regular grid pattern via simple folds. The conclusion is that, given an overlapping order for all the boundary triangular faces of the grid pattern, it is possible to determine in $O(m+n)^2$ time whether a simple folding process can achieve a compatible flat-folded state, with the boundary triangular faces overlapping in the given order.
Received: July 1, 2025
Accepted: August 4, 2025
References
[1] Hugo A. Akitaya, Kenneth C. Cheung, Erik D. Demaine, Takashi Horiyama, Thomas C. Hull, Jason S. Ku, Tomohiro Tachi and Ryuhei Uehara, Box pleating is hard, In Japanese Conference on Discrete and Computational Geometry and Graphs, Springer, 2015, pp. 167-179.
[2] H. A. Akitaya, E. D. Demaine and J. S. Ku, Simple folding is really hard, Journal of Information Processing 25 (2017), 580-589.
[3] E. M. Arkin, M. A. Bender, E. D. Demaine, M. L. Demaine, J. S. B. Mitchell, S. Sethia and S. S. Skiena, When Can You Fold a Map? Computational Geometry: Theory and Applications 29 (2002), 23-46.
[4] M. Bern and B. Hayes, The complexity of flat origami, In Ann. ACM-SIAM Symposium on Discrete Algorithms, ACM, 1996, pp. 175-183.
[5] Erik D. Demaine, Satyan L. Devadoss, Joseph S. B. Mitchell and Joseph O’Rourke, Continuous foldability of polygonal paper, In CCCG, 2004, pp. 64-67.
[6] Yiyang Jia and Jun Mitani, A comparison of different folding models in variations of the map folding problem, Applied Sciences 11(24) (2021), 11856.
[7] Yiyang Jia, Jun Mitani and Ryuhei Uehara, Valid orderings of layers when simple-folding a map, Journal of Information Processing 28 (2020), 816-824.
[8] Yiyang Jia, Jun Mitani and Ryuhei Uehara, Research on map folding with boundary order on simple fold, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 104(9) (2021), 1116-1126.
[9] Yiyang Jia, Map Folding Variations: Flat-foldability of Box-pleated Patterns and Validity of Overlapping Orders, Ph. D. Thesis, University of Tsukuba, 2021.
[10] R. I. Nishat, Map Folding, Master Thesis, University of Victoria, 2013.
Downloads
Published
Issue
Section
License
Copyright (c) 2025 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA
This work is licensed under a Creative Commons Attribution 4.0 International License.
_________________________
Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.
Contact Pushpa Publishing House for more info or permissions.
Journal Impact Factor: 
