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