**Reference**:- Jason Cantarella, Erik D. Demaine, Hayley Iben, and James O'Brien, “An Energy-Driven Approach to Linkage Unfolding”, in
*Proceedings of the 20th Annual ACM Symposium on Computational Geometry (SoCG 2004)*, Brooklyn, New York, June 9–11, 2004, pages 134–143. **Abstract**:-
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, radicals, and
trigonometric functions). (2) Each linear step of the motion can be
computed exactly in
*O*(*n*^{2}) time on a real RAM where*n*is the number of vertices. (3) We explicitly bound the number of linear steps (and hence the 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 [1] that implements the algorithm. **Comments**:- This paper is also available from the ACM Digital Library.
See also animations and a Java applet implementation of this algorithm.

**Updates**:- Michael Zilske and Günter Rote have another implementation as a Java applet that draws the trace of vertices.
**Length**:- The paper is 10 pages.
**Availability**:- The paper is available in PostScript (513k), gzipped PostScript (184k), and PDF (317k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- ForceLinkage_CGW2002 (An Energy-Driven Approach to Linkage Unfolding)
- Refolding_SIGGRAPH2004 (Refolding Planar Polygons)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.