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), rising space O(n). These time and space complexities are optimal. |
Year | Venue | Keywords |
---|---|---|
2002 | IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | linkage, planar reconfiguration., monotone tree |
DocType | Volume | Issue |
Journal | E85A | 5 |
ISSN | Citations | PageRank |
0916-8508 | 1 | 0.63 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yoshiyuki Kusakari | 1 | 10 | 3.34 |
Masaki Sato | 2 | 1 | 1.30 |
Takao Nishizeki | 3 | 1771 | 267.08 |