View source for Carpenter's rule problem

{{short description|On continuous motion of a simple polygon to convex}}
The '''carpenter's rule problem''' is a [[discrete geometry]] problem, which can be stated in the following manner: ''Can a [[simple polygon|simple planar polygon]] be moved continuously to a position where all its vertices are in [[convex position]], so that the edge lengths and simplicity are preserved along the way?'' A closely related problem is to show that any non-self-crossing [[polygonal chain]] can be straightened, again by a continuous transformation that preserves edge distances and avoids crossings.

Both problems were successfully solved by {{harvtxt|Connelly|Demaine|Rote|2003}}.

The problem is named after the multiple-jointed wooden [[ruler]]s popular among carpenters in the 19th and early 20th centuries before improvements to metal [[tape measure]]s made them obsolete.

==Combinatorial proof==
Subsequently, to their work, [[Ileana Streinu]] provided a simplified combinatorial proof formulated in the terminology of robot arm [[motion planning]]. Both the original proof and Streinu's proof work by finding non-expansive motions of the input, continuous transformations such that no two points ever move towards each other. Streinu's version of the proof adds edges to the input to form a [[pointed pseudotriangulation]], removes one added convex hull edge from this graph, and shows that the remaining graph has a one-parameter family of motions in which all distances are nondecreasing. By repeatedly applying such motions, one eventually reaches a state in which no further expansive motions are possible, which can only happen when the input has been straightened or convexified.

{{harvtxt|Streinu|Whiteley|2005}} provide an application of this result to the [[mathematics of paper folding]]: they describe how to fold any single-vertex [[origami]] shape using only simple non-self-intersecting motions of the paper. Essentially, this folding process is a time-reversed version of the problem of convexifying a polygon of length smaller than π, but on the surface of a sphere rather than in the Euclidean plane. This result was extended by {{harvtxt|Panina|Streinu|2010}} for spherical polygons of edge length smaller than 2π.

==Generalization==
{{harvs|first=John|last=Pardon|authorlink=John Pardon|year=2009|txt}} generalized the Carpenter's rule problem to [[rectifiable curve]]s. He showed that every rectifiable [[Jordan curve]] can be made convex, without increasing its length and without decreasing the distance between any pair of points. This research, performed while he was still a high school student, won the second-place prize for Pardon in the 2007 [[Intel Science Talent Search]] {{harv|Cunningham|2007}}.

==See also==
*[[Curve-shortening flow]], a continuous transformation of a closed curve in the plane that eventually convexifies it

==References==
*{{citation
 | last1 = Connelly | first1 = Robert | author1-link = Robert Connelly
 | last2 = Demaine | first2 = Erik D. | author2-link = Erik Demaine
 | last3 = Rote | first3 = Günter
 | doi = 10.1007/s00454-003-0006-7
 | issue = 2
 | journal = [[Discrete and Computational Geometry]]
 | mr = 1931840
 | pages = 205–239
 | title = Straightening polygonal arcs and convexifying polygonal cycles
 | url = http://page.mi.fu-berlin.de/~rote/Papers/pdf/Straightening+polygonal+arcs+and+convexifying+polygonal+cycles-DCG.pdf
 | volume = 30
 | year = 2003| doi-access = free
 }}. Preliminary version appeared at [[Symposium on Foundations of Computer Science|41st Annual Symposium on Foundations of Computer Science]], 2000.
*{{citation|first=Aimee|last=Cunningham|title=The Next Generation|journal=[[Science News]]|date=17 March 2007|page=166|doi=10.1002/scin.2007.5591711108 }}.
*{{citation
 | last = Streinu
 | first = Ileana
 | author-link = Ileana Streinu
 | contribution = A combinatorial approach to planar non-colliding robot arm motion planning
 | contribution-url = http://aigaion.geometry.cs.umass.edu//api/pdf_export.php?ID=16&apikey=6a91f2983e0877c86981f52d5c34fbce5b9507fe
 | doi = 10.1109/SFCS.2000.892132
 | mr = 1931841
 | pages = 443–453
 | publisher = IEEE Computer Society
 | title = Proceedings of the 41st Annual Symposium on Foundations of Computer Science
 | year = 2000
 | isbn = 0-7695-0850-2
 | s2cid = 9420124
 | url = https://scholarworks.smith.edu/cgi/viewcontent.cgi?article=1288&context=csc_facpubs
 | url-access = subscription
 }}
*{{citation
 | last1 = Panina | first1 = Gaiane
 | last2 = Streinu | first2 = Ileana | author2-link = Ileana Streinu
 | arxiv = 1003.3490
 | doi = 10.1016/j.comgeo.2010.04.002 | doi-access=free
 | issue = 8
 | journal = [[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]
 | mr = 1931841
 | pages = 678–687
 | title = Flattening single-vertex origami: The non-expansive case
 | volume = 43
 | year = 2010}}
*{{citation
 | last = Pardon | first = John | authorlink = John Pardon
 | doi = 10.1090/S0002-9947-08-04781-8
 | issue = 4
 | journal = [[Transactions of the American Mathematical Society]]
 | mr = 2465815
 | pages = 1749–1764
 | title = On the unfolding of simple closed curves
 | volume = 361
 | year = 2009| arxiv = 0809.1404| s2cid = 230031 }}.
*{{citation
 | last1 = Streinu | first1 = Ileana | author1-link = Ileana Streinu
 | last2 = Whiteley | first2 = Walter | author2-link = Walter Whiteley
 | contribution = Single-vertex origami and spherical expansive motions
 | mr = 2212105
 | pages = 161–173
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = Discrete and Computational Geometry: Japanese Conference, JCDCG 2004, Tokyo, Japan, October 8-11, 2004, Revised Selected Papers
 | volume = 3742
 | year = 2005}}

== External links ==
* [http://erikdemaine.org/linkage/animations/ Erik Demaine's page with animations of the straightening motion applied to some linkages]

[[Category:Discrete geometry]]
[[Category:Recreational mathematics]]
[[Category:Mathematical problems]]
[[Category:Mathematics of rigidity]]