The carpenter's rule problem is a

discrete geometry Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geome ...

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 In discrete and computational geometry, a set of points in the Euclidean plane or a higher-dimensional Euclidean space is said to be in convex position or convex independent if none of the points can be represented as a convex combination of the o ...

, 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 In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points (A_1, A_2, \dots, A_n) called its vertices. The curve itself consists of the line segments co ...

can be straightened, again by a continuous transformation that preserves edge distances and avoids crossings. Both problems were successfully solved by .

Combinatorial proof

Subsequently to their work,

Ileana Streinu Ileana Streinu is a Romanian-American computer scientist and mathematician, the Charles N. Clark Professor of Computer Science and Mathematics at Smith College in Massachusetts.

provided a simplified combinatorial proof formulated in the terminology of robot arm

motion planning Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used ...

. 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. provide an application of this result to the

mathematics of paper folding The discipline of origami or paper folding has received a considerable amount of mathematical study. Fields of interest include a given paper model's flat-foldability (whether the model can be flattened without damaging it), and the use of paper f ...

: they describe how to fold any single-vertex

origami ) is the Japanese paper art, art of paper folding. In modern usage, the word "origami" is often used as an inclusive term for all folding practices, regardless of their culture of origin. The goal is to transform a flat square sheet of pape ...

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 for spherical polygons of edge length smaller than 2π.

Generalization

generalized the Carpenter's rule problem to

rectifiable curve Rectification has the following technical meanings: Mathematics * Rectification (geometry), truncating a polytope by marking the midpoints of all its edges, and cutting off its vertices at those points * Rectifiable curve, in mathematics * Rec ...

s. He showed that every rectifiable

Jordan curve In mathematics, a curve (also called a curved line in older texts) is an object similar to a line, but that does not have to be straight. Intuitively, a curve may be thought of as the trace left by a moving point. This is the definition that a ...

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 The Regeneron Science Talent Search, known for its first 57 years as the Westinghouse Science Talent Search, and then as the Intel Science Talent Search (Intel STS) from 1998 through 2016, is a research-based science competition in the United Sta ...

References

*. Preliminary version appeared at 41st Annual Symposium on Foundations of Computer Science, 2000. *. * * *. *{{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

Erik Demaine's page with animations of the straightening motion applied to some linkages
Discrete geometry Recreational mathematics Mathematical problems Mathematics of rigidity

Combinatorial proof

Generalization

See also

References

External links