Paper by Erik D. Demaine
- Oswin Aichholzer, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, Mark Overmars, Michael A. Soss, and Godfried T. Toussaint, “Reconfiguring Convex Polygons”, Computational Geometry: Theory and Applications, volume 20, number 1–2, October 2001, pages 85–95. Special issue of selected papers from the 12th Annual Canadian Conference on Computational Geometry, 2000.
We prove that there is a motion from any convex polygon to any convex polygon
with the same counterclockwise sequence of edge lengths, that preserves the
lengths of the edges, and keeps the polygon convex at all times. Furthermore,
the motion is “direct” (avoiding any intermediate canonical
configuration like a subdivided triangle) in the sense that each angle changes
monotonically throughout the motion. In contrast, we show that it is
impossible to achieve such a result with each vertex-to-vertex distance
changing monotonically. We also demonstrate that there is a motion between
any two such polygons using three-dimensional moves known as pivots, although
the complexity of the motion cannot be bounded as a function of the number of
vertices in the polygon.
- This paper is also available from ScienceDirect.
- The paper is \copyright Elsevier Science B.V.
- The paper is 13 pages.
- The paper is available in PostScript (254k) and gzipped PostScript (89k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- CCCG2000c (Reconfiguring Convex Polygons)
- Related webpages:
- Carpenter's Rule Theorem
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 16, 2018 by