| Item type |
SIG Technical Reports(1) |
| 公開日 |
1991-07-22 |
| タイトル |
|
|
タイトル |
ソートされた点集合の凸包を求める最適並列アルゴリズム |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Optimal Parallel Algorithms for Finding the Convex Hull of a Sorted Point Set |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
大阪大学基礎工学部情報工学科 |
| 著者所属 |
|
|
|
大阪大学基礎工学部情報工学科 |
| 著者所属 |
|
|
|
大阪大学基礎工学部情報工学科 |
| 著者所属 |
|
|
|
大阪大学基礎工学部情報工学科 |
| 著者所属(英) |
|
|
|
en |
|
|
Faculty of Engineering Science, Osaka University |
| 著者所属(英) |
|
|
|
en |
|
|
Faculty of Engineering Science, Osaka University |
| 著者所属(英) |
|
|
|
en |
|
|
Faculty of Engineering Science, Osaka University |
| 著者所属(英) |
|
|
|
en |
|
|
Faculty of Engineering Science, Osaka University |
| 著者名 |
陳, 慰
中野, 浩嗣
増澤, 利光
都倉, 信樹
|
| 著者名(英) |
Wei, Chen
Koji, Nakano
Toshimitsu, Masuzawa
Nobuki, Tokura
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本稿では，まず，平面上のソートされた点集合の凸包を求める問題について考察し，以下の並列アルゴリズムを示す．（） EREW PRAM 上のn/log n プロセッサ，O(g ） 時間のアルゴリズム．（） CRCW PRAM 上の n/log log n プロセッサ，O(g log n．） 時間のアルゴリズム．（） CRCW PRAM 上のn^<1+e>プロセッサ，O（）時間のアルゴリズム，アルゴリズム（）と（）は最適であり，アルゴリズム（）は，プロセッサ数を多く用いるが，より高速である．また，アルゴリズム（），（），（）に簡単な変更を加えることにより，同じ計算量で，単純多角形の凸包を求めるアルゴリズムが得られる． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
This paper presents several parellel algorithms for finding the conves hull of a sorted planar point set: (1) the algorithm which runs in O(log n) time using n/log n processors on a EREW PRAM, (2) the algorithm which runs in O(log log n) time using n-log log n processors on a CRCW PRAM, (3) the algorithm which runs in O(1)time using n^<1+e> processors on a CRCW PRAM. The algorithms (1) and (2) are optimal, and if enough processors are availble, the algorithm (3) is faster. Moreover, without increasing the complexity, algorithms (1),(2) and (3) can be simply modified to find the convex hull of a simple polygon, rrespectively. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL）
巻 1991,
号 69(1991-AL-022),
p. 1-8,
発行日 1991-07-22
|
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL91022004 (1.5 MB)
