Paper by Erik D. Demaine

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.

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(n2) 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.

This paper is also available from the ACM Digital Library.

See also animations and a Java applet implementation of this algorithm.

Michael Zilske and Günter Rote have another implementation as a Java applet that draws the trace of vertices.

The paper is 10 pages.

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.
These pages are generated automagically from a BibTeX file.
Last updated March 9, 2018 by Erik Demaine.