Back to Search
Start Over
Folding a Paper Strip to Minimize Thickness
- Source :
- arXiv
- Publication Year :
- 2015
- Publisher :
- Elsevier, 2015.
-
Abstract
- In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to twometrics:minimizing the total number of layers in the folded state (so that a “flat folding” is indeed close toflat), andminimizing the total amount of paper required to execute the folding (where “thicker” creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.<br />National Science Foundation (U.S.). Origami Design for Integration of Self-assembling Systems for Engineering Innovation (grant EFRI- 124038)<br />National Science Foundation (U.S.). Expedition grant (CCF-1138967)<br />United States. Department of Defense. National Defense Science and Engineering Graduate (NDSEG) Fellowship (32 CFR 168a)
- Subjects :
- Computational Geometry (cs.CG)
FOS: Computer and information sciences
paper folding
0102 computer and information sciences
02 engineering and technology
Topology
01 natural sciences
Theoretical Computer Science
NP completeness
symbols.namesake
Exponential growth
crease width
Computer Science - Data Structures and Algorithms
0202 electrical engineering, electronic engineering, information engineering
Discrete Mathematics and Combinatorics
Data Structures and Algorithms (cs.DS)
Mathematics
NP-complete
computational origami
Planar graph
rigid origami
Computational Theory and Mathematics
010201 computation theory & mathematics
symbols
Computer Science - Computational Geometry
020201 artificial intelligence & image processing
linkage
optimization problem
Subjects
Details
- Language :
- English
- ISSN :
- 15708667
- Volume :
- 36
- Database :
- OpenAIRE
- Journal :
- Journal of Discrete Algorithms
- Accession number :
- edsair.doi.dedup.....6fdc1d68e225041c10b9dfe33fae4f0a