1-2hit |
A linkage is a collection of line segments, called bars, possibly joined at their ends, called joints. We consider flattening a tree-like linkage, that is, a continuous motion of their bars from an initial configuration to a final configuration looking like a"straight line segment," preserving the length of each bar and not crossing any two bars. In this paper, we introduce a new class of linkages, called "radial trees," and show that there exists a radial tree which cannot be flattened.
Yoshiyuki KUSAKARI Masaki SATO Takao NISHIZEKI
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.