Paper by Erik D. Demaine

Reference:

Hayley N. Iben, James F. O'Brien, and Erik D. Demaine, “Refolding Planar Polygons”, Discrete & Computational Geometry, volume 41, number 3, April 2009, pages 444–460. Special issue of selected papers from the 22nd Annual ACM Symposium on Computational Geometry, 2006.

BibTeX

@Article{Refolding_DCG,
  AUTHOR        = {Hayley N. Iben and James F. O'Brien and Erik D. Demaine},
  TITLE         = {Refolding Planar Polygons},
  JOURNAL       = {Discrete \& Computational Geometry},
  journalurl    = {http://link.springer.de/link/service/journals/00454/},
  VOLUME        = 41,
  NUMBER        = 3,
  MONTH         = {April},
  YEAR          = 2009,
  PAGES         = {444--460},
  NOTE          = {Special issue of selected papers from the 22nd Annual ACM
                   Symposium on Computational Geometry, 2006.},

  replaces      = {Refolding_SoCG2006},
  doi           = {https://dx.doi.org/10.1007/s00454-009-9145-7},
  dblp          = {https://dblp.org/rec/journals/dcg/IbenOD09},
  comments      = {See also
                   <A HREF="http://www.cs.berkeley.edu/b-cam/Papers/Iben-2006-RPP/">animations</A> of this algorithm.
                   <P>
                   This paper is also available from <A HREF="http://dx.doi.org/10.1007/s00454-009-9145-7">SpringerLink</A>.},
  papers        = {Refolding_SoCG2006; Refolding_SIGGRAPH2004; ForceLinkage_SoCG2004},
}

Abstract:

This paper describes an algorithm for generating a guaranteed-intersection-free interpolation sequence between any pair of compatible polygons. Our algorithm builds on prior results from linkage unfolding, and if desired it can ensure that every edge length changes monotonically over the course of the interpolation sequence. The computational machinery that ensures against self-intersection is independent from a distance metric that determines the overall character of the interpolation sequence. This decoupled approach provides a powerful control mechanism for determining how the interpolation should appear, while still assuring against intersection and guaranteeing termination of the algorithm. Our algorithm also allows additional control by accommodating a set of algebraic constraints that can be weakly enforced throughout the interpolation sequence.

Comments: