AN APPROXIMATE MORPHING BETWEEN POLYLINES
Sergey Bereg · International Journal of Computational Geometry & Applications · 2005
We consider the problem of continuously transforming or morphing one simple polyline into another polyline 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. The width of a morphing is defined as the longest geodesic path between corresponding points of the polylines. The optimization problem is to compute a morphing that minimizes the width. We present a linear-time algorithm for finding a morphing with width guaranteed to be at most two times the minimum width of a morphing. This improves the previous algorithm10 by a factor of log n. We develop a linear-time algorithm for computing a medial axis separator. We also show that the approximation factor is less than two for κ-straight polylines.