二つの凸多角形の重なりを求める最適な並列アルゴリズム

概要

論文の詳細を見る
重なり問題とは,図形が与えられた時,互いに重なる(交わる,共通部分を持つ)図形が存在するかどうかを判定したり,重なりを列挙したりする問題である.重なり問題は計算幾何学における最も基本的な問題であるばかりでなく,地理情報処理,VLSIのCAD,コンピュータ・グラフィックスの分野でも重要な問題である.二つの凸多角形の重なり(共通部分)を求める問題は重なり問題の中でも基本的な問題の一つである.従来の結果によると,凸n角形Pと凸m角形Qとの共通部分を求める逐次アルゴリズムの時間計算量は⊝(n+m)である.さらに,CREW-PRAM(複数のプロセッサが1つの共有メモリに接続しており各プロセッサは任意のメモリセルにアクセスできる.但し,同時読み出し可,同時書き込み不可)の上でこの問題を解く,時間計算量O(log(n+m)),プロセッサ数O(n+m)の並列アルゴリズムも提案されている.同問題に対して,本稿では,CREW-PRAMの上で,計算時間O(log(n+m)),プロセッサ数O((n+m)/(log(n+m)))の並列アルゴリズムを提案する.この並列アルゴリズムは,計算時間とプロセッサ数の積が,既知の最高速の逐次アルゴリズムの計算時間とオーダ的に一致するので,最適な加速(optimal speed-up)である.
一般社団法人情報処理学会の論文
1990-09-04