ソート点集合の凸包を求める定数通信ラウンドの並列アルゴリズム

概要

論文の詳細を見る
本稿ではソート点集合の凸包を求める決定性の並列アルゴリズムを提案し, また, そのアルゴリズムの関連問題への応用を考える.これらのアルゴリズムは, 実用的なモデルとして近年注目を集めているCGMモデルを用いて提案を行なう.まず最初に, ソート点集合の凸包について, n / p>___-P^2という条件に対し, 定数通信ラウンドのコスト最適なアルゴリズムを提案する.ここで, n.pはそれぞれ入力サイズ, プロセッサ数を表す.次に, n / p>___-p`e, かつ, 0<e<2という条件についても同じ計算量のより複雑な並列アルゴリズムを示し, これらのアルゴルズムより, n / p>___-P^e, かつe>0という条件に対し, 内部計算時間O(n / p), 及び, 定数通信ラウンドでソート点集合の凸包を計算できることを示す.最後に, これらの凸包アルゴリズムの応用として, 入力がd本の直線上に存在する凸層問題が, 内部計算時間O(<n log n>/ p), 及び, 定数通信ラウンド解けることを示す.このアルゴリズムも, その計算量よりコスト最適な並列アルゴリズムである.
社団法人電子情報通信学会の論文
2000-07-18