Pseudo Triangulations

The Carpenter's Rule Problem

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?

Algorithm for Convexifying a Simple Planar Polygon using Mechanisms Induced by Pseudo Triangulations

This animation illustrates the algorithmic solution to this problem, as described in my paper A Combinatorial Approach to Planar Non-Colliding Robot Arm Motion Planning , see FOCS 2000 extended abstract .

The first pseudo-triangulation-based mechanism of this motion (Cinderella animation) can be seen here. Such a mechanism has the property that as long as its acyclicity property of is preserved, it moves in such a way that the interdistances between any pair of vertices either all increase or all decrease (or stay the same). More animations to come soon.

Animation created together with my student Elif Tosun. Elif received the Best Student Poster Award at the CCSCNE'01 conference at Middlebury College, April 27-28, 2001, for this work. Drawings and mechanisms created using the Cinderella software. Improved versions to be posted here soon.