| Item type |
SIG Technical Reports(1) |
| 公開日 |
1992-07-17 |
| タイトル |
|
|
タイトル |
ソートされた点集合の接頭部凸包を求める最適並列アルゴリズム |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Optimal Parallel Algorithm for Computing the Prefix Convex Hulls of A Sorted Points 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 |
|
内容記述 |
ソートされた平面点集合が与えられたとき，その点集合の凸包をPRAM CREWの上，O(）時間，n/log nプロセッサで求める最適並列アルゴリズムが既に知られている．本研究で提案する並列アルゴリズムは，その点集合の全ての接頭部の凸包をCREW PRAMの上，O(g ）時間，n/log nプロセッサで求める．このアルゴリズムは最適である． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
The optimal parallel algorithm for computing the convex hull of a sorted set S of n points in the plane is known to be executed in O(log n) time using n/log n processors on the CREW PRAM. In this paper we present a parallel algorithm for computing the convex hulls of all prefix sets of S. The algorithm runs in O(log n) time using n/log n processors on the CREW PRAM, and hence is asymptotically optimal. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL）
巻 1992,
号 58(1992-AL-028),
p. 77-84,
発行日 1992-07-17
|
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL92028010 (1.4 MB)
