Carpenter's ruler problem

Carpenter's ruler problem

The carpenter's ruler 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.

Subsequently to their work, Ileana Streinu provided a simplified combinatorial proof. 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 Whitely (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.

References

*cite journal
author = Connelly, Robert; Demaine, Erik D.; Rote, Günter
title = Straightening polygonal arcs and convexifying polygonal cycles
journal = Discrete and Computational Geometry
volume = 30
issue = 2
year = 2003
pages = 205–239
id = Preliminary version appeared at 41st Annual Symposium on Foundations of Computer Science, 2000
url = http://page.mi.fu-berlin.de/~rote/Papers/pdf/Straightening+polygonal+arcs+and+convexifying+polygonal+cycles-DCG.pdf
doi = 10.1007/s00454-003-0006-7

*cite conference
author = Streinu, Ileana
title = A combinatorial approach to planar non-colliding robot arm motion planning
booktitle = Proceedings of the 41st Annual Symposium on Foundations of Computer Science
publisher = IEEE Computer Society
date = 2000
pages = 443–453
doi = 10.1109/SFCS.2000.892132
url = http://cs.smith.edu/~streinu/Papers/motion.ps

*cite conference
author = Streinu, Ileana; Whiteley, Walter
title = Single-vertex origami and spherical expansive motions
booktitle = Discrete and Computational Geometry
pages = 161–173
publisher = Springer-Verlag, Lecture Notes in Computer Science 3742
year = 2005
id = MathSciNet | id = 2212105


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Ruler — For other uses, see Ruler (disambiguation). A variety of rulers A 2 meter …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Pseudotriangle — In Euclidean plane geometry, a pseudotriangle is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation is a partition of a region of the plane into pseudotriangles, and a pointed… …   Wikipedia

  • Robert Connelly — Robert (Bob) 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. Connelly received his …   Wikipedia

  • Measurement — For bust/waist/hip measurement, see BWH. A typical tape measure with both metric and US units and two US pennies for comparison Measurement is the process or the result of determining the ratio of a physical quantity, such as a length, time,… …   Wikipedia

  • Europe, history of — Introduction       history of European peoples and cultures from prehistoric times to the present. Europe is a more ambiguous term than most geographic expressions. Its etymology is doubtful, as is the physical extent of the area it designates.… …   Universalium

  • ancient Greek civilization — ▪ historical region, Eurasia Introduction       the period following Mycenaean civilization, which ended in about 1200 BC, to the death of Alexander the Great, in 323 BC. It was a period of political, philosophical, artistic, and scientific… …   Universalium

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • Mexico — /mek si koh /, n. 1. a republic in S North America. 97,563,374; 761,530 sq. mi. (1,972,363 sq. km). Cap.: Mexico City. 2. a state in central Mexico. 6,245,000; 8268 sq. mi. (21,415 sq. km). Cap.: Toluca. 3. Gulf of, Mexican, Golfo de México /gawl …   Universalium

  • Calendar of 2002 — ▪ 2003 January I will not wait on events while dangers gather. I will not stand by as peril draws closer and closer. The United States of America will not permit the world s most dangerous regimes to threaten us with the world s most destructive… …   Universalium

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”