放射状の木の自動生成アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2005-07-13
• タイトル: 放射状の木の自動生成アルゴリズム
• タイトル / 言語: en
• タイトル: An Algorithm for Generating Radial Trees
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 秋田県立大学
• 著者所属: 秋田県立大学
• 著者所属: 秋田県立大学
• 著者所属: 秋田県立大学
• 著者所属(英): en
• 著者所属(英): Akita Prefectural University
• 著者所属(英): en
• 著者所属(英): Akita Prefectural University
• 著者所属(英): en
• 著者所属(英): Akita Prefectural University
• 著者所属(英): en
• 著者所属(英): Akita Prefectural University
• 著者名: 草苅, 良至; 新里, 善美; 能登谷, 淳一; 笠井, 雅夫
• 著者名(英): Yoshiyuki, Kusakari; Yoshimi, Niisato; Junichi, Notoya; Masao, Kasai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 近年 難しい問題に対して 問題例(インスタンス)の自動生成アルゴリズムの研究が行なわれている.一方 Altらは木状折れ線図形の直線化可能性の判定問題がPSPACE困難であることを示している.ここで 木状折れ線図形の直線化可能性問題とは，「平面上の木に対して 各辺の長さを変化させず辺同士を交差させずに 2次元平面上の連続的な変形で直線状にできるのか?」を判定する問題である.この問題に対して 限定されたクラス``放射状の木''が考えられている.そこで本稿では，放射状の木を自動生成するアルゴリズムを与える.提案アルゴリズムは平面走査法に基づいており n個のバーを持つ放射状の木を，O(n)の領域量を用いてO(n log n)時間で生成する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recently,some algorithms have been developed for generating instances of difficult problems,such as NP-hard or PSPACE-hard.Alt et.al. have showed that the decision problem for flattening the tree linkage,that is,whether the tree linkage could be flattened or not without crossing any two bars.For such problem, the ``radial tree'' is considered. In this paper, we give an algorithm for generating a radial tree T,in time O(n log n) using space O(n) if T has n joints. Our algorithm is a plane sweep type algorithm using a circle instead of a line.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2005, 号 67(2005-DBS-137), p. 77-84, 発行日 2005-07-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会