Title

Morphing Binary Trees

Authors

John Hershberger, Washington University in St Louis
Subhash Suri, Washington University in St Louis

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1994-01-01

Filename

WUCS-94-30.PDF

DOI:

10.7936/K72N50GK

Technical Report Number

WUCS-94-30

Abstract

We investigate the problem of transforming one binary tree into another by rotatoins, subject to certain weight ocnstraints on the nodes of the trees. These constraints arise in the problem of "morphing" one simple polygon to another simple polygon by continuous deformatinos (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(n4/3 + ε) rotations.

Comments

Permanent URL: http://dx.doi.org/10.7936/K72N50GK

Recommended Citation

Hershberger, John and Suri, Subhash, "Morphing Binary Trees" Report Number: WUCS-94-30 (1994). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/351