Given two non-intersecting simple polylines in the plane, we study
the problem of continuously transforming or morphing one polyline
into the other. Our morphing strategies have the desirable property
that every intermediate polyline is also simple. We also guarantee
that no portion of the polylines to be morphed is stretched or
compressed by more than a user-defined parameter during the entire
morphing. Our algorithms are based on the morphing width, a new
metric we have developed for measuring the similarity between two
polylines. We develop an algorithm that computes the morphing width
of the two polylines and constructs a corresponding morphing
strategy in time
using space, where is
the total number of vertices in the polylines. We describe another
algorithm that computes a factor- approximation of the morphing
width and a corresponding morphing scheme in time.
You can download the SODA version of the paper.