{"created":"2025-01-18T23:01:38.267462+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00032585","sets":["1164:2592:2707:2710"]},"path":["2710"],"owner":"10","recid":"32585","title":["ソートされた点集合の凸包を求める最適並列アルゴリズム"],"pubdate":{"attribute_name":"公開日","attribute_value":"1991-07-22"},"_buckets":{"deposit":"50efc53b-af14-4bdf-9314-48db1ca0597e"},"_deposit":{"id":"32585","pid":{"type":"depid","value":"32585","revision_id":0},"owners":[10],"status":"published","created_by":10},"item_title":"ソートされた点集合の凸包を求める最適並列アルゴリズム","author_link":["471597","471600","471596","471599","471598","471601","471595","471594"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"ソートされた点集合の凸包を求める最適並列アルゴリズム"},{"subitem_title":"Optimal Parallel Algorithms for Finding the Convex Hull of a Sorted Point Set","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"1991-07-22","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"大阪大学基礎工学部情報工学科"},{"subitem_text_value":"大阪大学基礎工学部情報工学科"},{"subitem_text_value":"大阪大学基礎工学部情報工学科"},{"subitem_text_value":"大阪大学基礎工学部情報工学科"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Faculty of Engineering Science, Osaka University","subitem_text_language":"en"},{"subitem_text_value":"Faculty of Engineering Science, Osaka University","subitem_text_language":"en"},{"subitem_text_value":"Faculty of Engineering Science, Osaka University","subitem_text_language":"en"},{"subitem_text_value":"Faculty of Engineering Science, Osaka University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/32585/files/IPSJ-AL91022004.pdf","label":"IPSJ-AL91022004"},"date":[{"dateType":"Available","dateValue":"1993-07-22"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL91022004.pdf","filesize":[{"value":"1.5 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"77d7030a-3e36-4b9b-96a9-e4d73f14c9e1","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 1991 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"陳, 慰"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"中野, 浩嗣"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"増澤, 利光"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"都倉, 信樹"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Wei, Chen","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Koji, Nakano","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Toshimitsu, Masuzawa","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Nobuki, Tokura","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"本稿では，まず，平面上のソートされた点集合の凸包を求める問題について考察し，以下の並列アルゴリズムを示す．（）　EREW　PRAM　上のn/log　n　プロセッサ，O(g　）　時間のアルゴリズム．（）　CRCW　PRAM　上の　n/log　log　n　プロセッサ，O(g　log　n．）　時間のアルゴリズム．（）　CRCW　PRAM　上のn^<1+e>プロセッサ，O（）時間のアルゴリズム，アルゴリズム（）と（）は最適であり，アルゴリズム（）は，プロセッサ数を多く用いるが，より高速である．また，アルゴリズム（），（），（）に簡単な変更を加えることにより，同じ計算量で，単純多角形の凸包を求めるアルゴリズムが得られる．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"1991-07-22","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"69(1991-AL-022)","bibliographicVolumeNumber":"1991"}]},"relation_version_is_last":true,"weko_creator_id":"10"},"id":32585,"updated":"2025-01-19T22:36:25.586316+00:00","links":{}}