Lecture 7: Fix for proof of Erdős-Nagy Theorem; characterizations of flat-foldable single-vertex crease patterns and mountain-valley patterns; continuous foldability of single-vertex patterns; linear-time algorithm for local foldability; NP-hardness of global foldability
Page 5: NP-hardness of global foldability: Bern and Hayes's reduction from not-all-equal 3-satisfiability
You can view the Bern and Hayes paper on local foldability and the complexity of global foldability.
These are rough, personal lecture notes handwritten by Erik Demaine used during lecture. Their primary purpose is for reading/review by students of the class. Accessibility
[<< prev lecture <<] -- [< prev page <] -- [> next page >] -- [>> next lecture >>] -- [up to index]