Geometric Folding Algorithms

<h2 id="audience">Audience</h2>
Although aimed at computer science and mathematics students,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> much of the book is accessible to a broader audience of mathematically-sophisticated readers with some background in high-school level geometry.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
Mathematical origami expert <a href="/facts/Tom_Hull_(mathematician)/ek7RyxVq">Tom Hull</a> has called it "a must-read for anyone interested in the field of computational origami".<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
It is a monograph rather than a textbook, and in particular does not include sets of exercises.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
The Basic Library List Committee of the <a href="/facts/Mathematical_Association_of_America/G3BkG5YX">Mathematical Association of America</a> has recommended this book for inclusion in undergraduate mathematics libraries.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="topics-and-organization">Topics and organization</h2>
The book is organized into three sections, on linkages, origami, and polyhedra.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a><a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
Topics in the section on linkages include
the <a href="/facts/Peaucellier%25E2%2580%2593Lipkin_linkage/aEqvUgV0">Peaucellier–Lipkin linkage</a> for converting rotary motion into linear motion,<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
<a href="/facts/Kempe%2527s_universality_theorem/lp2u6BqI">Kempe's universality theorem</a> that any <a href="/facts/Algebraic_curve/LnWsPmDP">algebraic curve</a> can be traced out by a linkage,<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a>
the existence of linkages for <a href="/facts/Angle_trisection/zSf98g6b">angle trisection</a>,<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>
and the <a href="/facts/Carpenter%2527s_rule_problem/93RNqj4t">carpenter's rule problem</a> on straightening two-dimensional <a href="/facts/Polygonal_chain/GRQ6BMQS">polygonal chains</a>.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>
This part of the book also includes applications to <a href="/facts/Motion_planning/DoSPv4dB">motion planning</a> for <a href="/facts/Robotic_arm/hGezrM9c">robotic arms</a>, and to <a href="/facts/Protein_folding/rf3nR2Y1">protein folding</a>.<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a><a class="footnote-ref" id="fnref:21" href="#fn:21">21</a>
The second section of the book concerns the <a href="/facts/Mathematics_of_paper_folding/Kfw9MCtU">mathematics of paper folding</a>, and mathematical <a href="/facts/Origami/anFEky9j">origami</a>. It includes the <a href="/facts/NP-complete/NFPv56DU">NP-completeness</a> of testing flat foldability,<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a>
the problem of <a href="/facts/Map_folding/WyzwN7TH">map folding</a> (determining whether a pattern of mountain and valley folds forming a square grid can be folded flat),<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a><a class="footnote-ref" id="fnref:24" href="#fn:24">24</a>
the work of <a href="/facts/Robert_J._Lang/G49XvPHd">Robert J. Lang</a> using tree structures and <a href="/facts/Circle_packing/nKFWD2ug">circle packing</a> to automate the design of origami folding patterns,<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a><a class="footnote-ref" id="fnref:26" href="#fn:26">26</a>
the <a href="/facts/Fold-and-cut_theorem/QL5l1BbL">fold-and-cut theorem</a> according to which any polygon can be constructed by folding a piece of paper and then making a single straight cut,<a class="footnote-ref" id="fnref:27" href="#fn:27">27</a><a class="footnote-ref" id="fnref:28" href="#fn:28">28</a>
origami-based angle trisection,<a class="footnote-ref" id="fnref:29" href="#fn:29">29</a>
<a href="/facts/Rigid_origami/czkRs8Th">rigid origami</a>,<a class="footnote-ref" id="fnref:30" href="#fn:30">30</a>
and the work of <a href="/facts/David_A._Huffman/4fbz13XB">David A. Huffman</a> on curved folds.<a class="footnote-ref" id="fnref:31" href="#fn:31">31</a>
In the third section, on <a href="/facts/Polyhedra/UC0p9FTF">polyhedra</a>, the topics include <a href="/facts/Net_(polyhedron)/lU8fmGJs">polyhedral nets</a> and Dürer's conjecture on their existence for convex polyhedra, the sets of polyhedra that have a given polygon as their net, <a href="/facts/Steinitz%2527s_theorem/FEq947FE">Steinitz's theorem</a> characterizing the graphs of polyhedra, <a href="/facts/Cauchy%2527s_theorem_(geometry)/JrvSbBtn">Cauchy's theorem</a> that every polyhedron, considered as a linkage of flat polygons, is rigid, and <a href="/facts/Alexandrov%2527s_uniqueness_theorem/W2LJ2MWg">Alexandrov's uniqueness theorem</a> stating that the three-dimensional shape of a convex polyhedron is uniquely determined by the <a href="/facts/Metric_space/gnBBRXtc">metric space</a> of <a href="/facts/Geodesic/fbWR6l80">geodesics</a> on its surface.<a class="footnote-ref" id="fnref:32" href="#fn:32">32</a>
The book concludes with a more speculative chapter on higher-dimensional generalizations of the problems it discusses.<a class="footnote-ref" id="fnref:33" href="#fn:33">33</a>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.gfalop.org/">Authors' web site for Geometric Folding Algorithms</a> including contents, errata, and advances on open problems</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Carbno, Collin (May 2009), "Review of Geometric Folding Algorithms", MAA Reviews, Mathematical Association of America <a href="https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra" target="_blank">https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">mbec (2011), "Review of Geometric Folding Algorithms", EMS Reviews, European Mathematical Society <a href="https://euro-math-soc.eu/review/geometric-folding-algorithms-linkages-origami-polyhedra" target="_blank">https://euro-math-soc.eu/review/geometric-folding-algorithms-linkages-origami-polyhedra</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Uehara, Ryuhei, 幾何的な折りアルゴリズム リンケージ・折り紙・多面体, retrieved 2020-02-02 <a href="http://www.jaist.ac.jp/~uehara/gfalop/" target="_blank">http://www.jaist.ac.jp/~uehara/gfalop/</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">mbec (2011), "Review of Geometric Folding Algorithms", EMS Reviews, European Mathematical Society <a href="https://euro-math-soc.eu/review/geometric-folding-algorithms-linkages-origami-polyhedra" target="_blank">https://euro-math-soc.eu/review/geometric-folding-algorithms-linkages-origami-polyhedra</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Hull, Tom (2012), "Other sources", Project Origami: Activities for Exploring Mathematics (2nd ed.), CRC Press, p. xviii <a href="/wiki/Tom_Hull_(mathematician)" target="_blank">/wiki/Tom_Hull_(mathematician)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Carbno, Collin (May 2009), "Review of Geometric Folding Algorithms", MAA Reviews, Mathematical Association of America <a href="https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra" target="_blank">https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Carbno, Collin (May 2009), "Review of Geometric Folding Algorithms", MAA Reviews, Mathematical Association of America <a href="https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra" target="_blank">https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Carbno, Collin (May 2009), "Review of Geometric Folding Algorithms", MAA Reviews, Mathematical Association of America <a href="https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra" target="_blank">https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Carbno, Collin (May 2009), "Review of Geometric Folding Algorithms", MAA Reviews, Mathematical Association of America <a href="https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra" target="_blank">https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">Carbno, Collin (May 2009), "Review of Geometric Folding Algorithms", MAA Reviews, Mathematical Association of America <a href="https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra" target="_blank">https://www.maa.org/press/maa-reviews/geometric-folding-algorithms-linkages-origami-polyhedra</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
<li id="fn:26">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></li>
<li id="fn:27">Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></li>
<li id="fn:28">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></li>
<li id="fn:29">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></li>
<li id="fn:30">Paquete, Luís (November 2009), "Review of Geometric Folding Algorithms", European Journal of Operational Research, 199 (1): 311–313, doi:10.1016/j.ejor.2008.06.009 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></li>
<li id="fn:31">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></li>
<li id="fn:32">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></li>
<li id="fn:33">Fasy, Brittany Terese; Millman, David L. (March 2011), "Review of Geometric Folding Algorithms", SIGACT News, 42 (1), Association for Computing Machinery: 43–46, doi:10.1145/1959045.1959056, S2CID 6514501 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></li>
</ol>

Geometric Folding Algorithms open-in-new

Geometric Folding Algorithms