"An Energy-Driven Approach to Linkage Unfolding"

We present a new algorithm for unfolding planar polygonal linkages without self-intersection based on following the gradient flow of a "repulsive" energy function. This algorithm has several advantages over previous methods. (1) The output motion is represented explicitly and exactly as a piecewise-linear curve in angle space. As a consequence, an exact snapshot of the linkage at any time can be extracted from the output in strongly polynomial time (on a real RAM supporting arithmetic, sin and arcsin). (2) Each linear step of the motion can be computed exactly in O(n2) time on a real RAM where n is the number of vertices. (3) We explicitly bound the number of linear steps (and hence running time) as a polynomial in n and the ratio between the maximum edge length and the initial minimum distance between a vertex and an edge. (4) Our method is practical and easy to implement. We provide a publicly accessible Java applet that implements the algorithm.



Cantarella, J. H., Demaine, E. D., Iben, H. N., and O'Brien, J. F., "An Energy-Driven Approach to Linkage Unfolding." The Proceedings of the 2004 Symposium on Computational Geometry, Brooklyn, New York, June 9-11, 2004.

Download PDF           BibTex 



Cantarella, J. H., Demaine, E. D., Iben, H. N., and O'Brien, J. F., "An Energy-Driven Approach to Linkage Unfolding." Proceedings of the 12th Annual DIMACS Workshop on Computational Geometry, Piscataway, New Jersey, November 14-15, 2002.

Download PDF           BibTex 

Examples

The following movies are DivX encoded.


The following images present a comparison of convexification between our energy method and CDR. To maximize visibility, the animation zooms as time proceeds; in fact, all edge lengths remain constant.

Teeth with energy method
(Movie)
Teeth with CDR method
Tree with energy method
(Movie)
Tree with CDR method



Here are some other examples of straightening and convexification computed with our energy-driven method. As before, the animation zooms as time proceeds to maximize visibility.

A spiral open chain
(Movie)

Tentacle
(Movie)

Spider
(Movie)



Applet

(using Euclidean distance metric)

Project Members

Jason H. Cantarella Erik D. Demaine James F. O'Brien Hayley N. Iben