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
following the gradient flow of a repulsive energy function.
physically based approach provides significant conceptual and
computational simplifications and improvements over previous
approaches. In particular, we give the first finite algorithm
constructing an explicit (piecewiselinear) motion to an outer-convex
configuration. The resulting piecewise-linear motion approximates
smooth (C1) motion, which was not previously known to exist.
algorithm is also the first whose running time is polynomial
sizes of its input and output, and can additionally be bounded
terms of the combinatorial and geometric complexity of the input,
such as the ratio between the largest and smallest distances
a vertex and an edge. Our method is practical and easy to
implement. We provide a publicly accessible Java
implements the algorithm.
Read a draft
of the paper