Origami research activities report (2007, 2008)
Research Achievements in Computational Origami Project in fiscal years 2007 - 2008
Formalization of Fold
Our work can be summarized as follows (from the abstract of the paper submitted for publication):
- Algebraic model for origami:
We formalize paper fold (origami) by graph rewriting. Origami construction is abstractly described by a rewriting system (O, f), where O is the set of abstract origami's and f is a binary relation on O, that models fold. An abstract origami is a structure (Π, ∼, >), where Π is a set of faces constituting an origami, and ∼ and > are binary relations on Π, each representing adjacency and superposition relations between the faces. - Graph-theoretic treatment of origami fold process:
We then address representation and transformation of abstract origami's and further reasoning about the construction for computational purposes. We present a labeled hypergraph of origami and define fold as algebraic graph transformation. The algebraic graph-theoretic formalism enables us to reason about origami in two separate domains of discourse, i.e. pure combinatorial domain where symbolic computation plays the main role and geometrical domain R x R. We detail the program language for the algebraic graph rewriting and graph rewriting algorithms for the fold, and show how fold is expressed by a set of graph rewrite rules.
Development of Web Environment for Computational Origami
We worked on building a web environment which enables interested origamists to manipulate origami through their web browsers, make new origami pieces, and reason about the geometrical properties of their constructions using methods from computer algebra. This led to the development of Origamium environment, which consists of the following integrated systems:
.
- Web E-Origami System (WebEos):
A system for constructing origami using interactive graphical web interfaces using Ajax technology, and allows users to demonstrate pre-made origami constructions and obtain their geometrical properties as polynomials. A beta version is available here (WebEos) - Symbolic Computation Research Forum (Scorum):
A Distributed system for symbolic computational web service, which provides access to web services for Maple and Mathematica implementations of Groebner Bases computation, which we use in origami reasoning and theorem proving. - E-Origami System (Eos):
Eos is the mathematical engine behind our environment, which performs the actual origami manipulation and visualization. It is written using Mathematica, and we developed special packages which integrate it with the other systems using webMathematica.
Algebraic Formalization of Computational Origami Construction
One of the foundational studies of the computational origami is the axiomatic definition of origami foldability inspired by Huzita's axioms. Huzita's axioms state the foldability of origami by asserting the existence of lines along which we can make a fold. A fold operation based on this axiomatic definition is performed along one single fold line.
- Formalization of origami construction:
We target a description of origami construction by a formal method. Therefore, we give a logical and algebraic formalization of Huzita's axioms. We define a many-sorted first-order logic language L and we specify its algebraic interpretation. Axioms are interpreted as set of polynomial equalities. Therefor, solving the polynomial equalities allow to find a fold line. We implemented a method HFold that allows the user to select one of the axiom and perform the fold operation. - Proof of the correctness of origami construction:
The polynomial are recorded during the construction steps. They form the premise of the theorem to be proved. The proof is based on algebraic theorem proving methods such as Groebner bases and cylindrical algebraic decomposition. - Towards the discovery of new fold methods:
Another fold method, called multifold method, extends the notion of foldability of origami paper. It allows making folds along multiple fold lines. The extension to the multifold is natural as HFold is implemented with the generality that allows the incorporation of the multifold. The multifold method can solve equation of degree higher than three. For instance, the quintisection of an angle was possible by multifold operations.
Publications
- Asem Kasem and Tetsuo Ida (2008): Computational Origami Environment on the Web - Frontiers of Computer Science in China 2(1):39-54.
- Tetsuo Ida, Mircea Marin, Hidekazu Takahashi, and Fadoua Ghourabi (2008): Computational Origami Construction as Constraint Solving and Rewriting - Electronic Notes in Theoretical Computer Science 216:31-44.
- Tetsuo Ida and Asem Kasem (2008): WEBEOS: A System for Origami Construction and Proving on the Web - The INTERNATIONAL INSTITUTE for ADVANCED STUDIES in SYSTEMS RESEARCH and CYBERNETICS, Tecumseh, Canada.
- Asem Kasem and Tetsuo Ida (2008): Experiences with Web Environment Origamium - In: Proceedings of the Annual Symposium of Japan Society for Software Science and Technology. JSSST, Tokyo, Japan.
- Fadoua Ghourabi, Tetsuo Ida and Hidekazu Takahashi (2008): Computational Origami of Angle Quintisection- In: Proceedings of the Annual Symposium of Japan Society for Software Science and Technology. JSSST, Tokyo, Japan.
- Tetsuo Ida, Hidekazu Takahashi, Mircea Marin, and Fadoua Ghourabi (2007): Modelling Origami for Computational Construction and Beyond - International Conference on Computational Science and Its Applications 2007 (ICCSA 2007) Lecture Notes in Computer Science(4706):653-665.
- Fadoua Ghourabi, Tetsuo Ida, Hidekazu Takahashi, Mircea Marin and Asem Kasem (2007): Logical and Algebraic View of Huzita's Origami Axioms with Applications to Computational Origami - In: Proceedings of the 22nd ACM Symposium on Applied Computing. ACM Press, pages 767-772.
- Monem Naifer, Asem Kasem and Tetsuo Ida (2007): A System of Web Services for Symbolic Computation - In: Proceedings of the 5th Asian Workshop on Foundations of Software. Beihang University, pages 145-152.