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