An Optimal Morphing between PolylinesAbstract: 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^{2})
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^{2}n. @article{b-ombp-02 , author = "S. Bespamyatnikh" , title = "An optimal morphing between polylines" , journal = "Int. J. Comput. Geom. Appls." , volume = 12 , number = 3 , pages = "217--228" , year = 2002 } |