| 講演名 | 1998/3/23 固定サイズの再構成メッシュ上で凸包を求めるアルゴリズム 笹田 良治, 松前 進, 都倉 信樹, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 再構成バス(reconfigurable bus system)とは, 形状を動的に変化させることのできるバスである.格子状に並べたプロセッサを再構成バスで接続したプロセッサアレイを再構成メッシュ(reconfigurable mesh)という.本稿では, 平面状のN個の点の凸包を, 大きさM×Mの再構成メッシュを用いて, O(N/M+N/M^2logN/M^2)時間で求めるアルゴリズムを示す(N[>|_]M).入力がx座標でソートされているときは, O(N/M)時間で求められる. |
| 抄録(英) | A reconfigurable bus system is a bus system whose configuration can be dynamically changed.A reconfigurable mesh is a processor array that consists of processors arranged to 2-dimensional grid with a reconfigurable bus system.In this paper, we present an algorithm for computing the convex hull of N points in the plane in O(N/M+N/M^2logN/M^2)time on a reconfigurable mesh of size M×M(N[>|_]M).In case the input sorted by x-coordinate, the convex hull can be computed in O(N/M)time. |
| キーワード(和) | 並列アルゴリズム / 再構成メッシュ / 凸包 |
| キーワード(英) | parallel algorithm / reconfigurable mesh / convex hull |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 1998/3/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 固定サイズの再構成メッシュ上で凸包を求めるアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A Convex Hull Algorithm on a Fixed Size Reconfigurable Mesh |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 並列アルゴリズム / parallel algorithm |
| キーワード(2)（和/英） | 再構成メッシュ / reconfigurable mesh |
| キーワード(3)（和/英） | 凸包 / convex hull |
| 第 1 著者 氏名（和/英） | 笹田 良治 / Ryoji Sasada |
| 第 1 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Graduate School of Engineering Science, Osaka University |
| 第 2 著者 氏名（和/英） | 松前 進 / Susumu Matsumae |
| 第 2 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Graduate School of Engineering Science, Osaka University |
| 第 3 著者 氏名（和/英） | 都倉 信樹 / Nobuki Tokura |
| 第 3 著者 所属（和/英） | 大阪大学大学院基礎工学研究科情報数理系専攻 Graduate School of Engineering Science, Osaka University |
| 発表年月日 | 1998/3/23 |
| 資料番号 | |
| 巻番号（vol） | vol.97 |
| 号番号（no） | 629 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |