Speaker: James O'Brien  (U.C. Berkeley)

An Energy-Driven Approach to Linkage Unfolding

  We present a new approach for straightening polygonal arcs and
  convexifying polygonal cycles without self-intersection based on
  following the gradient flow of a repulsive energy function. Our
  physically based approach provides significant conceptual and
  computational simplifications and improvements over previous
  approaches. In particular, we give the first finite algorithm for
  constructing an explicit (piecewiselinear) motion to an outer-convex
  configuration. The resulting piecewise-linear motion approximates a
  smooth (C1) motion, which was not previously known to exist. Our
  algorithm is also the first whose running time is polynomial in the
  sizes of its input and output, and can additionally be bounded in
  terms of the combinatorial and geometric complexity of the input,
  such as the ratio between the largest and smallest distances between
  a vertex and an edge. Our method is practical and easy to
  implement. We provide a publicly accessible Java applet that
  implements the algorithm.

Read a draft of the paper