| 講演名 | 2005-07-13 放射状の木の自動生成アルゴリズム(空間データ, 夏のデータベースワークショップ2005) 草苅 良至, 新里 善美, 能登谷 淳一, 笠井 雅夫, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年, 難しい問題に対して, 問題例(インスタンス)の自動生成アルゴリズムの研究が行なわれている.一方, Altらは木状折れ線図形の直線化可能性の判定問題がPSPACE困難であることを示している[2].ここで, 木状折れ線図形の直線化可能性問題とは, 「平面上の木に対して, 各辺の長さを変化させず辺同士を交差させずに, 2次元平面上の連続的な変形で直線状にできるのか?」を判定する問題である.この問題に対して, 限定されたクラス"放射状の木"が考えられている[9].そこで本稿では, 放射状の木を自動生成するアルゴリズムを与える.提案アルゴリズムは平面走査法に基づいており, n個のバーを持つ放射状の木を, O(n)の領域量を用いてO(n log n)時間で生成する. |
| 抄録(英) | 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 [2]. For such problem, the "radial tree" is considered [9]. 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. |
| キーワード(和) | インスタンス生成 / PSPASE困難 / NP困難 / 折れ線図形 / 直線化 / 単調な木 / 放射状の木 |
| キーワード(英) | instance generation / PSPACE-hard / NP-hard / linkage / flattening / monotone tree / radial tree |
| 資料番号 | DE2005-40 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2005/7/6(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 放射状の木の自動生成アルゴリズム(空間データ, 夏のデータベースワークショップ2005) |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm for Generating Radial Trees |
| サブタイトル（和） | |
| キーワード(1)（和/英） | インスタンス生成 / instance generation |
| キーワード(2)（和/英） | PSPASE困難 / PSPACE-hard |
| キーワード(3)（和/英） | NP困難 / NP-hard |
| キーワード(4)（和/英） | 折れ線図形 / linkage |
| キーワード(5)（和/英） | 直線化 / flattening |
| キーワード(6)（和/英） | 単調な木 / monotone tree |
| キーワード(7)（和/英） | 放射状の木 / radial tree |
| 第 1 著者 氏名（和/英） | 草苅 良至 / Yoshiyuki KUSAKARI |
| 第 1 著者 所属（和/英） | 秋田県立大学システム科学技術学部電子情報システム学科 Department of Electronics and Information Systems, Faculty of Systems Science and Thechnology, Akita Prefectural University |
| 第 2 著者 氏名（和/英） | 新里 善美 / Yoshimi NIISATO |
| 第 2 著者 所属（和/英） | 秋田県立大学大学院システム科学技術研究科電子情報システム学専攻 Department of Electronics and Information Systems, Graduate School of Systems Science and Thechnology, Akita Prefectural University |
| 第 3 著者 氏名（和/英） | 能登谷 淳一 / Junichi NOTOYA |
| 第 3 著者 所属（和/英） | 秋田県立大学システム科学技術学部電子情報システム学科 Department of Electronics and Information Systems, Faculty of Systems Science and Thechnology, Akita Prefectural University |
| 第 4 著者 氏名（和/英） | 笠井 雅夫 / Masao KASAI |
| 第 4 著者 所属（和/英） | 秋田県立大学システム科学技術学部電子情報システム学科 Department of Electronics and Information Systems, Faculty of Systems Science and Thechnology, Akita Prefectural University |
| 発表年月日 | 2005-07-13 |
| 資料番号 | DE2005-40 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 171 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |