Reconfiguring convex polygons

Written with Oswin Aichholzer, Erik D. Demaine, Ferran Hurtado, Mark Overmars, Michael A. Soss, and Godfried Toussaint.
Computational Geometry: Theory and Applications 20(1-2):85-95, 2001.
(Special issue of invited papers from the 12th Annual Canadian Conference on Computational Geometry)

Extended abstract in Proceedings of the 12th Annual Canadian Conference on Computational Geometry, 17-20, 2000.

Technical Report UU-CS-2000-30, Department of Computer Science, Utrecht University, 2000.

Abstract:
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 conguration 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.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Oct 2002