IEICE TRANSACTIONS on Information
Efficient Enumeration of Flat-Foldable Single Vertex Crease Patterns
Summary :
We investigate enumeration of distinct flat-foldable crease patterns under the following assumptions: positive integer n is given; every pattern is composed of n lines incident to the center of a sheet of paper; every angle between adjacent lines is equal to 2π/n; every line is assigned one of “mountain,” “valley,” and “flat (or consequently unfolded)”; crease patterns are considered to be equivalent if they are equal up to rotation and reflection. In this natural problem, we can use two well-known theorems for flat-foldability: the Kawasaki Theorem and the Maekawa Theorem in computational origami. Unfortunately, however, they are not enough to characterize all flat-foldable crease patterns. Therefore, so far, we have to enumerate and check flat-foldability one by one using computer. In this study, we develop the first algorithm for the above stated problem by combining these results in a nontrivial way and show its analysis of efficiency.
- Publication
- IEICE TRANSACTIONS on Information Vol.E102-D No.3 pp.416-422
- Publication Date
- 2019/03/01
- Publicized
- 2018/10/31
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2018FCP0004
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)
- Category
Authors
Koji OUCHI
Japan Advanced Institute of Science and Technology
Ryuhei UEHARA
Japan Advanced Institute of Science and Technology
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Koji OUCHI, Ryuhei UEHARA, "Efficient Enumeration of Flat-Foldable Single Vertex Crease Patterns" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 3, pp. 416-422, March 2019, doi: 10.1587/transinf.2018FCP0004.
Abstract: We investigate enumeration of distinct flat-foldable crease patterns under the following assumptions: positive integer n is given; every pattern is composed of n lines incident to the center of a sheet of paper; every angle between adjacent lines is equal to 2π/n; every line is assigned one of “mountain,” “valley,” and “flat (or consequently unfolded)”; crease patterns are considered to be equivalent if they are equal up to rotation and reflection. In this natural problem, we can use two well-known theorems for flat-foldability: the Kawasaki Theorem and the Maekawa Theorem in computational origami. Unfortunately, however, they are not enough to characterize all flat-foldable crease patterns. Therefore, so far, we have to enumerate and check flat-foldability one by one using computer. In this study, we develop the first algorithm for the above stated problem by combining these results in a nontrivial way and show its analysis of efficiency.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018FCP0004/_p
Copy
@ARTICLE{e102-d_3_416,
author={Koji OUCHI, Ryuhei UEHARA, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Enumeration of Flat-Foldable Single Vertex Crease Patterns},
year={2019},
volume={E102-D},
number={3},
pages={416-422},
abstract={We investigate enumeration of distinct flat-foldable crease patterns under the following assumptions: positive integer n is given; every pattern is composed of n lines incident to the center of a sheet of paper; every angle between adjacent lines is equal to 2π/n; every line is assigned one of “mountain,” “valley,” and “flat (or consequently unfolded)”; crease patterns are considered to be equivalent if they are equal up to rotation and reflection. In this natural problem, we can use two well-known theorems for flat-foldability: the Kawasaki Theorem and the Maekawa Theorem in computational origami. Unfortunately, however, they are not enough to characterize all flat-foldable crease patterns. Therefore, so far, we have to enumerate and check flat-foldability one by one using computer. In this study, we develop the first algorithm for the above stated problem by combining these results in a nontrivial way and show its analysis of efficiency.},
keywords={},
doi={10.1587/transinf.2018FCP0004},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Efficient Enumeration of Flat-Foldable Single Vertex Crease Patterns
T2 - IEICE TRANSACTIONS on Information
SP - 416
EP - 422
AU - Koji OUCHI
AU - Ryuhei UEHARA
PY - 2019
DO - 10.1587/transinf.2018FCP0004
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2019
AB - We investigate enumeration of distinct flat-foldable crease patterns under the following assumptions: positive integer n is given; every pattern is composed of n lines incident to the center of a sheet of paper; every angle between adjacent lines is equal to 2π/n; every line is assigned one of “mountain,” “valley,” and “flat (or consequently unfolded)”; crease patterns are considered to be equivalent if they are equal up to rotation and reflection. In this natural problem, we can use two well-known theorems for flat-foldability: the Kawasaki Theorem and the Maekawa Theorem in computational origami. Unfortunately, however, they are not enough to characterize all flat-foldable crease patterns. Therefore, so far, we have to enumerate and check flat-foldability one by one using computer. In this study, we develop the first algorithm for the above stated problem by combining these results in a nontrivial way and show its analysis of efficiency.
ER -
English
