Paper by Erik D. Demaine

Reference:

Erik D. Demaine and Martin L. Demaine, “Computing Extreme Origami Bases”, Technical Report CS-97-22, Department of Computer Science, University of Waterloo, May 1997.

BibTeX

@TechReport{ConvexExtremeTR,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine},
  TITLE         = {Computing Extreme Origami Bases},
  INSTITUTION   = {Department of Computer Science, University of Waterloo},
  institutionurl = {http://www.cs.uwaterloo.ca/},
  NUMBER        = {CS-97-22},
  numberurl     = {http://www.cs.uwaterloo.ca/cs-archive/CS-1997/CS-1997.shtml#22},
  MONTH         = {May},
  YEAR          = 1997,

  length        = {18 pages},
  webpages      = {foldcut},
  updates       = {This work on the fold-and-cut problem has been
                   generalized to arbitrary plane graphs; see my
                   <A HREF="../../foldcut/">fold-and-cut
                   webpage</A> for links to related papers.
                   <P>
                   Further updates concerning this technical report:
                   <UL>
                   <LI> In joint work with Therese Biedl, Martin Demaine,
                     Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins,
                     Ileana Streinu, Godfried Toussaint, and Sue Whitesides,
                     it has been shown that general trees linkages cannot
                     always be straightened (disallowing extra folds); see the
                     <a href="../CCCG98c">CCCG'98 paper</a>.
                     This solves the open problem mentioned in Section 5.3,
                     but does not disprove the closed-chain conjecture as
                     claimed in this technical report.  In fact, the
                     closed-chain conjecture is true; see my
                     <A HREF="../../linkage/">linkage
                     webpage</A>.
                   </LI>
                   <LI> In joint work with Marshall Bern, David Eppstein, and
                     Barry Hayes, the first part of Conjecture 1 has been
                     disproved: it is possible to combine several "local"
                     bisector graphs (instead of using one "global" one) to
                     solve the folding-and-cutting problem.  See the
                     <a href="../FUN98">FUN'98 paper</a>.
                   </LI>
                   </UL>}
}

Abstract:

In this paper, we examine extreme origami bases that fold the boundary of a polygonal sheet of paper to a common plane, generalizing the Husimi and Meguro molecules used in origami design. This also solves the folding-and-cutting problem, where we want to make a specified polygon by one complete straight cut after arbitrary folding of a square sheet of paper. We present an algorithm to construct the crease pattern of an extreme base for paper in the shape of an arbitrary simple polygon. It is based on the straight skeleton, a variant on the medial axis. For convex polygons, we describe exactly how the folding process can be performed. This proves that the folding can even be done with paper that is rigid except at the creases, and allows animation of the folding process. Such descriptions have not been achieved before for an infinite class of origamis.

Updates:

This work on the fold-and-cut problem has been generalized to arbitrary plane graphs; see my fold-and-cut webpage for links to related papers.

Further updates concerning this technical report:

• In joint work with Therese Biedl, Martin Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, and Sue Whitesides, it has been shown that general trees linkages cannot always be straightened (disallowing extra folds); see the CCCG'98 paper. This solves the open problem mentioned in Section 5.3, but does not disprove the closed-chain conjecture as claimed in this technical report. In fact, the closed-chain conjecture is true; see my linkage webpage.
• In joint work with Marshall Bern, David Eppstein, and Barry Hayes, the first part of Conjecture 1 has been disproved: it is possible to combine several "local" bisector graphs (instead of using one "global" one) to solve the folding-and-cutting problem. See the FUN'98 paper.

Length:

The paper is 18 pages.

Availability:

The paper is available in PostScript (471k), gzipped PDF (580k), and ZIPped PDF (580k).

See information on file formats.

[Google Scholar search]

Related webpages:

The Fold-and-Cut Problem