The search functionality is under construction.

The search functionality is under construction.

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yoshiyuki KUSAKARI, Masaki SATO, Takao NISHIZEKI, "Planar Reconfiguration of Monotone Trees" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 938-943, May 2002, doi: .

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_938/_p

Copy

@ARTICLE{e85-a_5_938,

author={Yoshiyuki KUSAKARI, Masaki SATO, Takao NISHIZEKI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Planar Reconfiguration of Monotone Trees},

year={2002},

volume={E85-A},

number={5},

pages={938-943},

abstract={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.},

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

TI - Planar Reconfiguration of Monotone Trees

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 938

EP - 943

AU - Yoshiyuki KUSAKARI

AU - Masaki SATO

AU - Takao NISHIZEKI

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E85-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 2002

AB - 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.

ER -