When can you fold a map?
type: Item
instance of: scholarly article
title: When can you fold a map?
zbMATH Open document ID: 1063.68099
author: Esther M. Arkin
author: Michael A. Bender
author: Erik D. Demaine
author: Martin L. Demaine
author: Joseph S. B. Mitchell
author: Saurabh Sethia
author: Steven Skiena
published in: Computational Geometry
publication date: 2004-10-13T00:00:00Z
review text: A crease pattern is a straight-edge embedding of a graph on a polygonal piece of paper, usually with specified mountain and valley assignments that give a folding direction; a flat folding must fold along all the edges of the graph, but no more. Characterizing flat-foldable crease patterns is the best-studied problem in origami mathematics and has a natural algorithmic counterpart consisting of determining whether a given crease pattern is flat-foldable. In this paper it is proved that deciding foldability of an orthogonal crease pattern on a rectangular piece of paper can be done in linear time, while slight variations, like having a general orthogonal piece of paper, 45-degree creases, or no mountain/valley assignment, gives NP-complete problems.
Mathematics Subject Classification ID: 68U05
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 51M15
Mathematics Subject Classification ID: 00A08
zbMATH DE Number: 2107419
zbMATH Keywords: computational origami
zbMATH Keywords: folding
reviewed by: Ferran Hurtado
MaRDI profile type: Publication
full work available at URL: j.comgeo.2004.03.012
OpenAlex ID: W2118063590
cites work: An algorithmic study of manufacturing paperclips and other folded structures.
cites work: Q4875182
cites work: Q4542582
cites work: Folding flat silhouettes and wrapping polyhedral packages: New results in computational origami
cites work: Folding and coloring problems in mathematics and physics
cites work: Q3322005
cites work: Q4198056
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: Q4863426
cites work: Efficient randomized pattern-matching algorithms
cites work: Folding a strip of stamps
cites work: A Map-Folding Problem
cites work: Multi-dimensional map-folding
cites work: Q4856179
cites work: On Finding Lowest Common Ancestors: Simplification and Parallelization
cites work: Q4250223
cites work: Contribution a L'etude Du Probleme Des Timbres Poste
DOI: 10.1016/J.COMGEO.2004.03.012
description: scientific article; zbMATH DE number 2107419