Morphing simple polygons (Q1577545)

Morphing two geometric shapes means finding a continuous deformation that transforms one shape into the other. This paper considers the problem of morphing two parallel simple polygons \(P\) and \(Q\) with \(n\) edges \(P_i\), \(Q_i\), \(i=1,\ldots,n\), where edge \(P_i\) is parallel to edge \(Q_i\), and all intermediate shapes are also parallel simple polygons with \(n\) edges. The main result is an \(O(n \log n)\) algorithm that determines for any such pair of simple polygons a morphing sequence of \(O(n \log n)\) elementary transformations, i.e., uniform scalings or translations. This article builds upon the proceedings versions by \textit{L. Guibas} and \textit{J. Hershberger} [Proc. ACM Symp. Comp. Geom., 267-276 (1994)], and \textit{J. Hershberger} and \textit{S. Suri} [Morphing binary trees. In: Clarkson, K. (ed.), Proceedings of the 6th annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, USA, January 22-24, 1995. Philadelphia, PA, 396-404 (1995; Zbl 0849.68093)].