{"created":"2023-05-15T12:35:46.377630+00:00","id":4820,"links":{},"metadata":{"_buckets":{"deposit":"c020e254-abcd-42bf-a171-0b1b77e9f4d4"},"_deposit":{"created_by":3,"id":"4820","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"4820"},"status":"published"},"_oai":{"id":"oai:nitech.repo.nii.ac.jp:00004820","sets":["31"]},"author_link":["15566","16289","8926"],"item_10001_biblio_info_28":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2000-04-20","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"4","bibliographicPageEnd":"732","bibliographicPageStart":"722","bibliographicVolumeNumber":"E83-A","bibliographic_titles":[{"bibliographic_title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"}]}]},"item_10001_description_36":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"Let S be a set of n points in the plane and CH(S) be the convex hull of S. We consider the problem of constructing an approximate convex hull which contains CH(S) with strong convexity. An ε-convex δ-superhull of S  is a convex polygon P satisfying the following conditions: (1) P  has at most O(n) vertices, (2) P contains S, (3) no vertex of P lies farther than δ outside CH(S), and (4) P remains convex even if its vertices are perturbed by as much as ε. The parameters ε and δ represent the strength of convexity of P and the degree of approximation of P to CH(S), respectively. This paper presents the first parallel method for the problem. We show that an ε-convex (8+42)ε-superhull of S can be constructed in O(log n) time using O(n) processors, or in O(log n) time using O(n/log n) processors if S is sorted, in the EREW-PRAM  model. We implement the algorithm and find that the average performance is even much better: the results are more strongly convex and much more approximate to CH(S) than the theoretical analysis shows.","subitem_description_type":"Other"}]},"item_10001_description_38":{"attribute_name":"フォーマット","attribute_value_mlt":[{"subitem_description":"application/pdf","subitem_description_type":"Other"}]},"item_10001_full_name_27":{"attribute_name":"著者別名","attribute_value_mlt":[{"nameIdentifiers":[{}],"names":[{"name":"和田, 幸一"}]}]},"item_10001_publisher_29":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Institute of Electronics, Information and Communication Engineers"}]},"item_10001_source_id_30":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"09168508","subitem_source_identifier_type":"ISSN"}]},"item_10001_source_id_32":{"attribute_name":"書誌レコードID（NCID）","attribute_value_mlt":[{"subitem_source_identifier":"AA10826239","subitem_source_identifier_type":"NCID"}]},"item_10001_version_type_33":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Castanho, Dense","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Chen, Wei","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Wada, Koichi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-01-24"}],"displaytype":"detail","filename":"E83-A_722.pdf","filesize":[{"value":"690.8 kB"}],"format":"application/pdf","license_note":"Copyright (c) 2000 IEICE　http://search.ieice.org/index.html","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"本文_fulltext","url":"https://nitech.repo.nii.ac.jp/record/4820/files/E83-A_722.pdf"},"version_id":"bb101977-b5a1-438b-8245-dd3ca1d3329b"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points","subitem_title_language":"en"}]},"item_type_id":"10001","owner":"3","path":["31"],"pubdate":{"attribute_name":"公開日","attribute_value":"2013-06-25"},"publish_date":"2013-06-25","publish_status":"0","recid":"4820","relation_version_is_last":true,"title":["A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points"],"weko_creator_id":"3","weko_shared_id":-1},"updated":"2023-05-16T14:42:41.825338+00:00"}