2026-03-11T13:51:23Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00032585 2025-01-19T22:36:25Z 1164:2592:2707:2710

ソートされた点集合の凸包を求める最適並列アルゴリズム Optimal Parallel Algorithms for Finding the Convex Hull of a Sorted Point Set 陳, 慰 中野, 浩嗣 増澤, 利光 都倉, 信樹 Wei, Chen Koji, Nakano Toshimitsu, Masuzawa Nobuki, Tokura 本稿では，まず，平面上のソートされた点集合の凸包を求める問題について考察し，以下の並列アルゴリズムを示す．（）　EREW　PRAM　上のn/log　n　プロセッサ，O(g　）　時間のアルゴリズム．（）　CRCW　PRAM　上の　n/log　log　n　プロセッサ，O(g　log　n．）　時間のアルゴリズム．（）　CRCW　PRAM　上のn^<1+e>プロセッサ，O（）時間のアルゴリズム，アルゴリズム（）と（）は最適であり，アルゴリズム（）は，プロセッサ数を多く用いるが，より高速である．また，アルゴリズム（），（），（）に簡単な変更を加えることにより，同じ計算量で，単純多角形の凸包を求めるアルゴリズムが得られる． This paper presents several parellel algorithms for finding the conves hull of a sorted planar point set: (1) the algorithm which runs in O(log n) time using n/log n processors on a EREW PRAM, (2) the algorithm which runs in O(log log n) time using n-log log n processors on a CRCW PRAM, (3) the algorithm which runs in O(1)time using n^<1+e> processors on a CRCW PRAM. The algorithms (1) and (2) are optimal, and if enough processors are availble, the algorithm (3) is faster. Moreover, without increasing the complexity, algorithms (1),(2) and (3) can be simply modified to find the convex hull of a simple polygon, rrespectively. technical report 情報処理学会 1991-07-22 application/pdf 情報処理学会研究報告アルゴリズム（AL） 69(1991-AL-022) 1991 1 8 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/32585/files/IPSJ-AL91022004.pdf jpn