Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Theory of Combinatorial Algorithms
Prof. Emo Welzl and Prof. Bernd Gärtner
Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
Straightening Chains and Convexifying Polygons
Erik Demaine, University of Waterloo
Place several rods down on the table, and hinge them together to make a chain. Is it always possible to rotate the hinges and move the links, in such a way that the links are straightened into a line? The links are not allowed to change length or cross each other. At first glance, it seems intuitive that any chain can be ``unraveled'' into a straight line, but experimentation reveals that this is a nontrivial problem.
This question has been open for many years, posed by several researchers including Joseph Mitchell, William Lenhart, and Sue Whitesides. A related question is, if we connect the rods in a cycle, can we move the links to make a convex polygon? This question seems even harder than straightening chains. This talk surveys the work done on both of these problems, and presents some new results.
Back
