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 polygon can be convexified, that is, continuously transformed, preserving edge distances and avoiding crossings, into a convex polygon.
Both problems were successfully solved by Connelly, Demaine & Rote (2000).
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π.
- Connelly, Robert; Demaine, Erik D.; Rote, Günter (2003). "Straightening polygonal arcs and convexifying polygonal cycles". 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.
- 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. MR 1931841.
- Panina, Gaiane; Streinu, Ileana (2010). "Flattening single-vertex origami: The non-expansive case". Comput. Geom. 43 (8): 678–687. arXiv:1003.3490. doi:10.1016/j.comgeo.2010.04.002. MR 1931841.
- Streinu, Ileana; Whiteley, Walter (2005). "Single-vertex origami and spherical expansive motions". Discrete and Computational Geometry. Springer-Verlag, Lecture Notes in Computer Science 3742. pp. 161–173. MR 2212105.