The search functionality is under construction.
The search functionality is under construction.

Planar Reconfiguration of Monotone Trees

Yoshiyuki KUSAKARI, Masaki SATO, Takao NISHIZEKI

  • Full Text Views

    0

  • Cite this

Summary :

A linkage is a collection of line segments, called bars, possibly joined at their ends, called joints. A planar reconfiguration of a linkage is a continuous motion of their bars, preserving the length of each bar and disallowing bars to cross. In this paper, we introduce a class of linkages, called "monotone trees," and give a method for reconfiguring a monotone tree to a straight line. If the tree has n joints, then the method takes at most n-1 moves, each of which uses two joints. We also obtain an algorithm to find such a method in time O(n log n), using space O(n). These time and space complexities are optimal.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.938-943
Publication Date
2002/05/01
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category

Authors

Keyword