Planar Reconfiguration of Monotone Trees(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

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

• 社団法人電子情報通信学会の論文
• 2002-05-01

著者

• Nishizeki Takao

  The Author Is With The Graduate School Of Information Science Tohoku University

• Nishizeki Takao

  The Author Is With Graduate School Of Information Sciences Tohoku University

• KUSAKARI Yoshiyuki

  The author is with the Department of Electronics and Information Systems, Faculty of Systems Science

• SATO Masaki

  The author is with Automatic Data Capture Division Eng. Dept., DENSO WAVE INCORPORATED

• Kusakari Yoshiyuki

  The Author Is With The Department Of Electronics And Information Systems Faculty Of Systems Science

• Sato Masaki

  The Author Is With Automatic Data Capture Division Eng. Dept. Denso Wave Incorporated

関連論文

• On the Average Length of Secret Key Exchange Eulerian Circuits(Special Section on Discrete Mathematics and Its Applications)
• Planar Reconfiguration of Monotone Trees(Special Section on Discrete Mathematics and Its Applications)
• Generalized Vertex-Colorings of Partial k-Tress(Special Section on Discrete Mathematics and Its Applications)

スポンサーリンク