skip to main content
10.1145/1529282.1529531acmconferencesArticle/Chapter ViewAbstractPublication PagessacConference Proceedingsconference-collections
research-article

Origami fold as algebraic graph rewriting

Published: 08 March 2009 Publication History

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, and G. Taentzer. Fundamentals of Algebraic Graph Transformation. Springer-Verlag, 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]
T. Ida, M. Marin, H. Takahashi, and F. Ghourabi. Computational Origami Construction as Constraint Solving and Rewriting. In Proceedings of the 16th International Workshop on Functional and (Constraint) Logic Programming, volume 216 of Electronic Notes in Theoretical Computer Science, pages 31--44. Elsevier B. V., 2008.
[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.

Cited By

View all
  • (2009)Symbolic and algebraic methods in computational origamiProceedings of the 2009 international symposium on Symbolic and algebraic computation10.1145/1576702.1576704(3-4)Online publication date: 28-Jul-2009
  • (2008)Graph Rewriting in Computational OrigamiProceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing10.1109/SYNASC.2008.86(20-27)Online publication date: 26-Sep-2008

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing
March 2009
2347 pages
ISBN:9781605581668
DOI:10.1145/1529282
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 March 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Origami
  2. geometric modeling
  3. graph rewriting
  4. hypergraph

Qualifiers

  • Research-article

Conference

SAC09
Sponsor:
SAC09: The 2009 ACM Symposium on Applied Computing
March 8, 2009 - March 12, 2008
Hawaii, Honolulu

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25
The 40th ACM/SIGAPP Symposium on Applied Computing
March 31 - April 4, 2025
Catania , Italy

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 13 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2009)Symbolic and algebraic methods in computational origamiProceedings of the 2009 international symposium on Symbolic and algebraic computation10.1145/1576702.1576704(3-4)Online publication date: 28-Jul-2009
  • (2008)Graph Rewriting in Computational OrigamiProceedings of the 2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing10.1109/SYNASC.2008.86(20-27)Online publication date: 26-Sep-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media