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