凸多角形内の全最遠近隣を求める並列アルゴリズム

概要

論文の詳細を見る
凸多角形内の全最遠近隣を求める問題とは,凸多角形Pが与えられたとき,Pの各頂点υについて,クリッド)距離が一番遠いPの頂点を求める問題である.本研究では,この問題を解く2つの並列を提案する.一つのアルゴリズムは,任意の凸多角形について,問題をEREW PRAM上で,O(log時間,n,log nプロセッサで解く.もう一つのアルゴリズムは,unimodal凸多角形(各頂点υに対し頂点との距離関数には一回しかローカル極大値が現れない凸多角形)について,問題を(i)CRCWO(log log n)時間,n/log log nプロセッサで,(ii)EREW PRAM上で,O(log n)時間,n/log nプロCRCW PRAM上で,O(1)時間,n^1+ε>(εは任意の正定数)で解く.また, O(n log^c n)プロセッサ(cはを用いるときに,CRCW PRAM上で,unimodal凸多角形内の全最遠近隣を求める時間計算量の下界であることを証明した.
社団法人電子情報通信学会の論文
1993-05-27