Graduate Research Talk: Geometric folding problems

Abstract

Computational Origami is a branch of computer science that focuses on folding related problems from an algorithmic perspective. Results in this area have applications from artistic origami design to robotics. In this work we determine the computational complexity of two origami related problems: flat foldability and simple foldability. Both problems have as input a crease pattern, i.e., a planar straight-line graph that represents the creases left in the paper after folding an origami. The first problem asks if a crease pattern can be folded into a flat state and the second asks if a crease pattern can be folded using a sequence of simple folds (mountain or valley folds). Finally, we describe interesting open problems in the area.