Morphing binary trees
John E. Hershberger, Subhash Suri · 1995
We investigate the problem of transforming one binary tree into another by rotations, subject to certain weight constraints on the nodes of the trees. These constraints arise in the problem of "morphing" one simple polygon to another simple polygon by continuous deformations (translations and scalings) that preserve the turn angles and the simplicity of the polygon; the two polygons must have the same sequence of turn angles. Our main theorem is that two arbitrary n-leaf binary trees satisfying our weight constraint can be morphed into each other with O(n log n) rotations. Furthermore, we also present an O(n log n) time algorithm to determine these rotations. The previous best algorithm for this problem used O(n 4=3+ffl ) rotations. 1 Introduction "Morphing," the continuous deformation of one shape to another, is a popular theme in computer graphics [1, 4, 5, 6]. A recent paper by Guibas and Hershberger [3] considers the problem of morphing a simple polygon P to another simple poly...