Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

1994-01-01

Filename

WUCS-94-30.PDF

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

Download

Share

COinS