Carpenter's ruler problem
Encyclopedia
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 Robert Connelly
, Erik Demaine
and Günter Rote in 2000.
. 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 and 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, but on the surface of a sphere rather than in the Euclidean plane.
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 geometric objects, such as points, lines, planes, circles,...
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
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
can be convexified, that is, continuously transformed, preserving edge distances and avoiding crossings, into a convex polygon.
Both problems were successfully solved by Robert Connelly
Robert Connelly
Robert Connelly is a mathematician specializing in discrete geometry and rigidity theory. He is best known for discovering embedded flexible polyhedra. One such polyhedron is in the National Museum of American History....
, Erik Demaine
Erik Demaine
Erik D. Demaine , is a professor of Computer Science at the Massachusetts Institute of Technology.-Early life:...
and Günter Rote in 2000.
Streinu's work
Subsequently to their work, Ileana Streinu provided a simplified combinatorial proof formulated in the terminology of robot arm motion planningMotion planning
Motion planning is a term used in robotics for the process of detailing a task into discrete motions....
. 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 and Whiteley (2005) provide an application of this result to the mathematics of paper folding
Mathematics of paper folding
The art of origami or paper folding has received a considerable amount of mathematical study. Fields of interest include a given paper model's flat-foldability and the use of paper folds to solve mathematical equations.-Flat folding:The construction of origami models is sometimes shown as crease...
: they describe how to fold any single-vertex origami
Origami
is the traditional Japanese art of paper folding, which started in the 17th century AD at the latest and was popularized outside Japan in the mid-1900s. It has since then evolved into a modern art form...
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, but on the surface of a sphere rather than in the Euclidean plane.