An Optimal Morphing between Polylines

Abstract: 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(n²) time using O(n) space, where n is the total number of vertices of polylines. This improves the previous algorithm [1] by a factor of log²n.

[1] A. Efrat, L. J. Guibas, S. Har-Peled, and T. M. Murali, Morphing between polylines, Proc. 12th ACM-SIAM Sympos. Discrete Algorithms, pp. 680-689, 2001.

Gzipped postscript file

@string{IJCGA    = "Int.\ J. Comput. Geom. Appls."} 

@article{b-ombp-02
, author = "S. Bespamyatnikh"
, title = "An optimal morphing between polylines"
, journal = IJCGA
, volume = 12
, number = 3
, pages = "217--228"
, year = 2002
}