Paper by Erik D. Demaine

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

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