AN OPTIMAL MORPHING BETWEEN POLYLINES
Sergei N. Bespamyatnikh · International Journal of Computational Geometry & Applications · 2002
We address the problem of continuously transforming or morphing one simple polyline into another so that every point p of the initial polyline moves to a point q of the final polyline using the geodesic shortest path from p to q. We optimize the width of the morphing, that is, the longest path made by a point on the polyline. We present an algorithm for finding the minimum width morphing in O(n2) time using O(n) space, where n is the total number of vertices of polylines. This improves the previous algorithm7 by a factor of log 2 n.