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.

BibTeX

@InProceedings{ForceLinkage_SoCG2004,
  AUTHOR        = {Jason Cantarella and Erik D. Demaine and Hayley Iben and
                   James O'Brien},
  TITLE         = {An Energy-Driven Approach to Linkage Unfolding},
  BOOKTITLE     = {Proceedings of the 20th Annual ACM Symposium on
                   Computational Geometry (SoCG 2004)},
  bookurl       = {http://socg.poly.edu/home.htm},
  MONTH         = {June 9--11},
  YEAR          = 2004,
  ADDRESS       = {Brooklyn, New York},
  PAGES         = {134--143},

  award         = {Invited to special issue of \emph{Discrete \& Computational Geometry}.},
  length        = {10 pages},
  papers        = {ForceLinkage_CGW2002; Refolding_SIGGRAPH2004},
  replaces      = {ForceLinkage_CGW2002},
  doi           = {https://dx.doi.org/10.1145/997817.997840},
  dblp          = {https://dblp.org/rec/conf/compgeom/CantarellaDIO04},
  comments      = {This paper is also available from the
                   <A HREF="http://doi.acm.org/10.1145/997817.997840">ACM Digital Library</A>.
                   <P>
                   See also
                   <A HREF="http://graphics.eecs.berkeley.edu/papers/Cantarella-AED-2004-06/">animations
                   and a Java applet implementation</A> of this algorithm.},
  updates       = {Michael Zilske and G&uuml;nter Rote have
                   <A HREF="http://page.mi.fu-berlin.de/zilske/linkages/">another
                   implementation as a Java applet</A> that draws the trace
                   of vertices.},
}

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