 |
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
|