Origami fold as algebraic graph rewriting

ABSTRACT

We formalize paper fold (origami) by graph rewriting. Origami construction is abstractly described by a rewriting system (O, ↬), where O is the set of abstract origami's and ↬ is a binary relation on O, called fold. An abstract origami is a triplet (Π, ∽, ≻), where Π is a set of faces constituting an origami, and ≻ and are binary relations on Π, each representing adjacency and superposition relations between the faces.

We then address representation and transformation of abstract origami's and further reasoning about the construction for computational purposes. We present a hypergraph of origami and define origami 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 combinatoric domain and geometric domain R x R, and thus helps us to further tackle challenging problems in computational origami research.

REFERENCES

• 1: R. C. Alperin. A Mathematical Theory of Origami Constructions and Numbers. New York Journal of Mathematics, 6: 119--133, 2000.
• 2: Erik D. Demaine and Martin L. Demaine. Recent Results in Computational Origami. In Proceedings of the Third International Meeting of Origami Science, Mathematics and Education, pages 3--16. A K Peters, Ltd., 2002.
• 3: H. Ehrig , K. Ehrig , U. Prange , G. Taentzer, Fundamentals of Algebraic Graph Transformation (Monographs in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: H. Huzita. Axiomatic Development of Origami Geometry. In Proceedings of the First International Meeting of Origami Science and Technology, pages 143--158, 1989.
• 5: Tetsuo Ida , Mircea Marin , Hidekazu Takahashi , Fadoua Ghoura, Computational Origami Construction as Constraint Solving and Rewriting, Electronic Notes in Theoretical Computer Science (ENTCS), 216, p.31-44, July, 2008 [doi>10.1016/j.entcs.2008.06.032]
• 6: T. Ida, H. Takahashi, M. Marin, and F. Ghourabi. Modeling Origami for Computational Construction and Beyond. In Proceedings of the 2007 International Conference on Computational Science and Its Applications, volume 4151 of Lecture Notes in Computer Science, pages 653--665. Springer-Verlag, 2007.
• 7: T. Ida, H. Takahashi, M. Marin, F. Ghourabi, and A. Kasem. Computational Construction of a Maximal Equilateral Triangle Inscribed in an Origami. In Proceedings of the Second International Congress on Mathematical Software, volume 4151 of Lecture Notes in Computer Science, pages 361--372. Springer-Verlag, 2006.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Keywords:
Origami, geometric modeling, graph rewriting, hypergraph