Morphing between Polylines

Alon Efrat, Sariel Har-Peled, Leonidas J. Guibas , and T.~M. Murali

We study the problem of continuously transforming or morphing two non-intersecting simple(not self-intersecting) polylines in the plane. Our morphing strategies have the 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 driven by a new metric for measuring the similarity between two polylines, which may have other applications. We compute morphing schemes that minimize this metric and also approximate the minimum value efficiently.

Postscript file

@string{SODA12  = "Proc. 12th ACM-SIAM Sympos. Discrete Algorithms"}

@InProceedings{eghm-mbp-01,
  author = {A.~Efrat and L.J.~Guibas and S.~Har-Peled and T.M.~Murali},
  title = {Morphing between Polylines},
  booktitle = SODA12,
  year = 2001,
  pages = {680-689}
}

Last modified: Fri Jul 7 17:11:46 EDT 2000