An approximate morphing between polylines

摘要

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 algorithm(10) 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.