An Energy-Driven Approach to Linkage Unfolding
- Jason Cantarella
- Erik Demaine
- Hayley Iben
- James F. O'Brien
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,
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.
Best paper award at SoCG 2004.
Jason H. Cantarella, Eric D. Demaine, Hayley N. Iben, and James F. O'Brien. "An Energy-Driven Approach to Linkage Unfolding". In Proceedings of the 20th Annual Symposium on Computational Geometry, June 2004.
Teeth with energy method.
Tree with energy method.
A spiral open chain.
Spider shape opening.
If your browser does not support the JRE plugin, then you may still be able to run this applet by installing the Java J2SE v 1.4 SDK and running the command "appletviewer" with this URL as the first argument in quotes: appletviewer "http://url_of_this_page.html" where you replace url_of_this_page with this page's address.