Introduction to Computational Origami - The World of New Computational Geometry

Description

This book focuses on origami from the point of view of computer science. Ranging from basic theorems to the latest research results, the book introduces the considerably new and fertile research field of computational origami as computer science. Part I introduces basic knowledge of the geometry of development, also called a net, of a solid. Part II further details the topic of nets. In the science of nets, there are numerous unresolved issues, and mathematical characterization and the development of efficient algorithms by computer are closely connected with each other. Part III discusses folding models and their computational complexity. When a folding model is fixed, to find efficient ways of folding is to propose efficient algorithms. If this is difficult, it is intractable in terms of computational complexity. This is, precisely, an area for computer science research. Part IV presents some of the latest research topics as advanced problems. Commentaries on all exercises included in the last chapter. The contents are organized in a self-contained way, and no previous knowledge is required. This book is suitable for undergraduate, graduate, and even high school students, as well as researchers and engineers interested in origami. Ryuhei Uehara is a professor in the School of Information Science at the Japan Advanced Institute of Science and Technology. After working as a researcher at Canon Inc., he joined Tokyo Woman's Christian University as an assistant professor. He was later a lecturer and associate professor at Komazawa University. He was a visiting scholar at the University of Waterloo (Canada), the Massachusetts Institute of Technology (USA), Simon Fraser University (Canada), Université libre de Bruxelles (Belgium), ETH Zürich (Switzerland), and Universitat Politècnica de Catalunya (Spain). His research interests include computational complexity, algorithms and data structures, and graph algorithms. He is especially engrossed in computational origami, games, and puzzles from the point of view of theoretical computer science. He is one of two translators of the New Martin Gardner Mathematical Library into Japanese. Preface......Page 5 About This Book......Page 8 Contents of This Book......Page 9 Assumed Reader in This Book......Page 10 Constructs of This Book......Page 11 Support Website......Page 12 Contents......Page 13 Part I Introduction to Unfolding......Page 17 1.1 Unfolding and Edge-Unfolding......Page 18 Reference......Page 22 2.1 Basic Properties of Unfolding......Page 23 2.2 The Number of Edge-Unfoldings......Page 25 2.3 Akiyama-Nara's Theorem......Page 27 2.3.1 Tetramonohedron by Acute Triangles......Page 31 2.3.2 Infinite Foldings by Rolling Belt......Page 32 References......Page 35 Part II Common Nets......Page 37 3.1 Some Preparations......Page 38 3.2 Common Nets of Two Boxes......Page 42 3.2.1 Random Generation Method of Spanning Trees......Page 43 3.2.2 Direct Search Algorithm for Common Nets......Page 44 3.2.3 Brute Force Search Algorithm......Page 48 3.3.1 Tiling Net......Page 49 3.3.3 Net Where Crease Lines Are Independent......Page 50 3.3.4 Infinite Nets......Page 51 3.3.5 More General Problems......Page 52 3.4 Common Nets of Three Boxes......Page 55 3.4.1 Search for Special Area 30......Page 58 3.4.2 Construction Based on a New Idea......Page 64 3.5 Summary of This Chapter and Open Problems......Page 67 3.6 Extra Problem......Page 70 References......Page 71 4.1 Classification of Regular Polyhedra......Page 72 4.1.1 Regular-Faced Convex Polyhedra......Page 73 4.2 Impossibility of Common Edge-Unfolding of Regular Polyhedra......Page 76 4.2.1 Proof of Theorem4.2.1......Page 78 4.3 Common Nets of Regular Tetrahedron and Cube......Page 81 4.3.1 Procedure for Generating Common Nets......Page 82 4.3.2 Summary of This Section and Future Work......Page 87 4.3.3 Bonus......Page 88 Reference......Page 89 Part III Algorithm and Complexity of Folding......Page 90 5.1 One-Dimensional Origami Model with Equivalent Spaced Creases......Page 93 5.1.1 Basic Theorems......Page 94 5.2 Universality of Simple Folding Model with Equivalent Spaced Creases......Page 96 5.3 Stamp Folding Problem......Page 100 5.3.1 Proof of Upper Bound......Page 102 5.3.2 Proof of Lower Bound......Page 104 References......Page 105 6.1 Folding Complexity of Stamp Folding......Page 106 6.1.1 Basic Properties of Folding Complexity......Page 108 6.1.2 Algorithms for Pleat Folding......Page 109 6.1.3 Algorithm and Lower Bound for General Patterns......Page 115 6.2 Crease Width of Stamp Folding......Page 119 6.2.1 Optimization Problem and Computational Complexity......Page 120 6.2.2 NP Completeness of the Minimization Problem of the Maximum Crease Width......Page 123 6.2.3 Tractability for Bounded k......Page 128 References......Page 131 Part IV Advanced Problems......Page 132 7.1 Convex Polyhedra Folded from a Polygon......Page 134 7.2 Petal Folding Problem......Page 135 7.3 Triangulation, Voronoi Diagram, and Power Diagram......Page 138 7.4 Preparation of Petal Pyramid Folding......Page 141 7.5 Folding Pyramid......Page 143 7.6 Four-Vertex Bumpy Pyramid Folding......Page 144 7.7 Folding Convex Pyramid......Page 148 7.8 Bumpy Pyramid of the Maximum Volume......Page 151 References......Page 153 8.1 Unfolding Along Hamilton Path......Page 154 8.3 Zipper-Unfolding......Page 155 8.3.1 Convex Polyhedra Which Cannot Be Unfolded by Zipper-Unfolding......Page 157 8.4 Summary of the Current States of Convex Polyhedron Unfoldable by Edge-Unfolding and Zipper-Unfolding......Page 163 References......Page 164 9.1 History and Preparation of the Rep-Cube......Page 165 9.2 Regular Rep-Cubes......Page 166 9.2.1 Enumeration of Regular Rep-Cubes......Page 171 9.3 Cases that There Is No Regular Rep-Cube......Page 172 9.3.1 Cases that Regular Rep-Cubes Are Likely to Exist and Not to Exist......Page 176 9.4.1 How to Construct Non-Regular Rep-Cubes......Page 177 9.4.2 Pythagorean Triples......Page 179 9.4.3 Five-Piece Solution for Pythagorean Triple......Page 180 9.5 Open Problems......Page 186 9.6 Extension to Doubly Covered Square and Regular Tetrahedron......Page 187 References......Page 190 10.1 Extension to Regular-Faced Convex Polyhedron......Page 191 10.1.2 Regular-Faced Convex Polyhedra Which Can Make p2 Tilings......Page 193 10.1.3 Regular-Faced Convex Polyhedra Having Common Developments with Regular Tetrahedron......Page 198 10.2 Enumeration of All Edge-Unfoldings of a Given Convex Polyhedron......Page 199 10.3.1 Folding Regular Tetrahedron......Page 201 10.3.3 Folding General Convex Polyhedron......Page 202 References......Page 205 11.1 Theoretical Model of Origami......Page 206 11.2 Diagonalization......Page 207 11.3 Undecidability of Halting Problem......Page 209 11.4 Undecidability of Origami Folding Problem......Page 212 Reference......Page 216 12 Answers to Exercises......Page 217 References......Page 225 Index......Page 226