誤差耐性のある強凸包構成問題に対する並列解法

• Item type: SIG Technical Reports(1)
• 公開日: 1995-03-17
• タイトル: 誤差耐性のある強凸包構成問題に対する並列解法
• タイトル / 言語: en
• タイトル: Parallel Methods for Constructing Strongly Convex Hull Using Exact and Rounded Arithmetic
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Computer Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Computer Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Computer Engineering, Nagoya Institute of Technology
• 著者名: 陳, 慰; 和田, 幸一; 川口, 喜三男
• 著者名(英): Wei, Chen; Koichi, Wada; Kimio, Kawaguchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面上にあるn個の点集合Sが与えられたとき，Sのε?強凸δ?包Pは次のように定義される凸多角形である：（）Pの頂点はSに属する，（）Pの外にあるSの点とPとの距離はδ以内である，(）Pの各頂点を任意に〓だけ移動してもPは凸である．本稿ではこの一般化した凸包問題を解く並列アルゴリズムを提案する．その結果として，Sのε?強凸O（ε）?包は，（）誤差のない演算を用いるときO(g ）時間，nプロセッサで求められる，（）丸め誤差を含む演算を用いるときO(g^)時間，nプロセッサで求められる．ここで提案する並列アルゴリズムは，逐次アルゴリズムとみなすと既知の逐次アルゴリズムと同じ計算時間でより正確な強凸包を求めることができるので，改良した新しい逐次アルゴリズムにもなる．本研究で用いる並列計算モデルはCREWPRAMである．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Theε-strongly convex δ-hull of a set S of n points in the plane is defined as a convex polygon P with the vertices taken from S such that no point of S lies farther than δ outside P and such that even if the vertices of P are perturbed by as much asε, P remains convex. In this paper we propose parallel methods for computing such a generalized convex hull. Using exact arithmetic we can construct anε-strongly convex O(ε)-hull in O(log n) time using n processors, and using rounded arithmetic we can construct anε-strongly convex O(ε+μ) -hull in O(log^3 n) time using n processors, where μ is the rounded unit. Our algorithms can be also taken as the improved sequential algorithms which run faster and compute the solution more precisely than the known sequential algorithms. The parallel computation model which we use in this paper is CREW PRAM.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1995, 号 32(1994-AL-044), p. 45-52, 発行日 1995-03-17
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会