Carpenter's rule problem
The carpenter's rule problem is a discrete geometry problem, which can be stated in the following manner: Can a 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 Connelly, Demaine & Rote (2003).

The problem is named after the multiple-jointed wooden rulers popular among carpenters in the 19th and early 20th centuries before improvements to metal tape measures 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.
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 Panina & Streinu (2010) for spherical polygons of edge length smaller than 2π.
Generalization
John Pardon (2009) generalized the Carpenter's rule problem to rectifiable curves. 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 (Cunningham 2007).
See also
- Curve-shortening flow, a continuous transformation of a closed curve in the plane that eventually convexifies it
References
- Connelly, Robert; Demaine, Erik D.; Rote, Günter (2003), "Straightening polygonal arcs and convexifying polygonal cycles" (PDF), Discrete and Computational Geometry, 30 (2): 205–239, doi:10.1007/s00454-003-0006-7, MR 1931840. Preliminary version appeared at 41st Annual Symposium on Foundations of Computer Science, 2000.
- Cunningham, Aimee (17 March 2007), "The Next Generation", Science News: 166, doi:10.1002/scin.2007.5591711108.
- Streinu, Ileana (2000), "A combinatorial approach to planar non-colliding robot arm motion planning", Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 443–453, doi:10.1109/SFCS.2000.892132, ISBN 0-7695-0850-2, MR 1931841, S2CID 9420124
- Panina, Gaiane; Streinu, Ileana (2010), "Flattening single-vertex origami: The non-expansive case", Computational Geometry: Theory and Applications, 43 (8): 678–687, arXiv:1003.3490, doi:10.1016/j.comgeo.2010.04.002, MR 1931841
- Pardon, John (2009), "On the unfolding of simple closed curves", Transactions of the American Mathematical Society, 361 (4): 1749–1764, arXiv:0809.1404, doi:10.1090/S0002-9947-08-04781-8, MR 2465815, S2CID 230031.
- Streinu, Ileana; Whiteley, Walter (2005), "Single-vertex origami and spherical expansive motions", Discrete and Computational Geometry: Japanese Conference, JCDCG 2004, Tokyo, Japan, October 8-11, 2004, Revised Selected Papers, Lecture Notes in Computer Science, vol. 3742, Springer-Verlag, pp. 161–173, MR 2212105
External links
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.