The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Une liaison est un ensemble de segments de ligne, appelés barres, éventuellement joints à leurs extrémités, appelés joints. Une reconfiguration planaire d'une liaison est un mouvement continu de leurs barres, préservant la longueur de chaque barre et interdisant aux barres de se croiser. Dans cet article, nous introduisons une classe de liaisons, appelées « arbres monotones », et donnons une méthode pour reconfigurer un arbre monotone en ligne droite. Si l'arbre a n articulations, alors la méthode prend au plus n-1 mouvements, dont chacun utilise deux articulations. On obtient également un algorithme pour trouver une telle méthode dans le temps O(n log n), en utilisant l'espace O(n). Ces complexités temporelles et spatiales sont optimales.
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.
Copier
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
Copier
@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},}
Copier
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 -