Optimal Morphs of Convex Drawings
A left-flat path Q (red thick line) and its elongation E(Q) (red and black thick lines)
We give an algorithm to compute a morph between any two convex drawings of the same plane graph. The morph preserves the convexity of the drawing at any time instant and moves each vertex along a piecewise linear curve with linear complexity. The linear bound is asymptotically optimal in the worst case.
References:
- Patrizio Angelini, Giordano Da Lozzo, Fabrizio Frati, Anna Lubiw, Maurizio Patrignani, Vincenzo Roselli. Optimal Morphs of Convex Drawings. In Proc. 31st Symposium on Computational Geometry (SoCG ’15), 2015. To appear.
