Ni hao! This section describes research that I have done in computational geometry.
Simple Fold and Cut.
The fold and cut problem asks what shapes can be made by taking a sheet of paper, folding it flat, and then making one complete straight cut across the paper. The general variant of this problem was solved by Bern, et al. in 1998 [1]. The general variant of the problem allows all folds that keep the final configuration of the paper flat. The simple variant of the problem allows only basic folds where single crease lines are generated in sequence; the all-layer variant requires that all folds go through all layers of the paper. My recent publication [2] develops a strongly polynomial time algorithm that determines whether a given polygon is all-layer simple fold and cuttable. We prove that the order of the folds does not affect the fold and cuttability of a polygon, thus enabling us to use a greedy algorithm. Our algorithm first searches for a line of symmetry and folds along the first symmetry line found. There are O(n) possible symmetry lines; this search takes O(n) time. Once a first fold has been made, we are left with a simple polygonal line with endpoints on the edge of the paper. We check for remaining feasible folds, determine marginal lines for the terminal edges, fold and repeat. Testing whether the remainder is simple-fold-and-cuttable takes O(n2) time, for a total time of O(n2). We also prove that a convex polygon is simple fold and cuttable if and only if it has a line of symmetry, as the marginal lines in this case allow folding until terminal edges are arbitrarily small. Finally, we demonstrate that the class of xy-monotone polyhedra are simple fold and cuttable. Results for the simple fold and cut problem can simplify automated manufacturing processes, like airbag folding, and may lead to insights into biological processes like protein folding. References
[1] Marshall Bern, Erik Demaine, David Eppstein, and Barry Hayes, “A Disk-Packing Algorithm for an Origami Magic Trick,” Proceedings of the International Conference on Fun with Algorithms (FUN’98), Isola d’Elba, Italy, June 18-20, 1998, pages 32-42. [2] Erik D. Demaine, Martin L. Demaine, Andrea Hawksley, Hiro Ito, Po-Ru Loh, Shelly Manber, and Omari Stephens, “Making Polygons by Simple Folds and One Straight Cut,” forthcoming, Abstracts from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), Dalian, China, November 36, 2010. Abstract
The fold and cut problem asks what shapes can be made by taking a sheet of paper, folding it flat, and then making one complete straight cut across the paper. The general variant of this problem was solved by Bern, et al. in 1998 [1]. The general variant of the problem allows all folds that keep the final configuration of the paper flat. The simple variant of the problem allows only basic folds where single crease lines are generated in sequence; the all-layer variant requires that all folds go through all layers of the paper. My recent publication [2] develops a strongly polynomial time algorithm that determines whether a given polygon is all-layer simple fold and cuttable. We prove that the order of the folds does not affect the fold and cuttability of a polygon, thus enabling us to use a greedy algorithm. Our algorithm first searches for a line of symmetry and folds along the first symmetry line found. There are O(n) possible symmetry lines; this search takes O(n) time. Once a first fold has been made, we are left with a simple polygonal line with endpoints on the edge of the paper. We check for remaining feasible folds, determine marginal lines for the terminal edges, fold and repeat. Testing whether the remainder is simple-fold-and-cuttable takes O(n2) time, for a total time of O(n2). We also prove that a convex polygon is simple fold and cuttable if and only if it has a line of symmetry, as the marginal lines in this case allow folding until terminal edges are arbitrarily small. Finally, we demonstrate that the class of xy-monotone polyhedra are simple fold and cuttable. Results for the simple fold and cut problem can simplify automated manufacturing processes, like airbag folding, and may lead to insights into biological processes like protein folding. References
[1] Marshall Bern, Erik Demaine, David Eppstein, and Barry Hayes, “A Disk-Packing Algorithm for an Origami Magic Trick,” Proceedings of the International Conference on Fun with Algorithms (FUN’98), Isola d’Elba, Italy, June 18-20, 1998, pages 32-42. [2] Erik D. Demaine, Martin L. Demaine, Andrea Hawksley, Hiro Ito, Po-Ru Loh, Shelly Manber, and Omari Stephens, “Making Polygons by Simple Folds and One Straight Cut,” forthcoming, Abstracts from the China-Japan Joint Conference on Computational Geometry, Graphs and Applications (CGGA 2010), Dalian, China, November 36, 2010. Abstract