WEKO3
アイテム
A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points
https://nitech.repo.nii.ac.jp/records/4820
https://nitech.repo.nii.ac.jp/records/48200bf5a9e9-e55b-42a0-b3b4-cb685d50d566
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
本文_fulltext (690.8 kB)
|
Copyright (c) 2000 IEICE http://search.ieice.org/index.html
|
| Item type | 学術雑誌論文 / Journal Article(1) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-06-25 | |||||||||||
| タイトル | ||||||||||||
| タイトル | A Parallel Algorithm for Constructing Strongly Convex Superhulls of Points | |||||||||||
| 言語 | en | |||||||||||
| 言語 | ||||||||||||
| 言語 | eng | |||||||||||
| 資源タイプ | ||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||
| 資源タイプ | journal article | |||||||||||
| 著者 |
Castanho, Dense
× Castanho, Dense
× Chen, Wei
× Wada, Koichi
|
|||||||||||
| 著者別名 | ||||||||||||
| 姓名 | 和田, 幸一 | |||||||||||
| bibliographic_information |
en : IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 巻 E83-A, 号 4, p. 722-732, 発行日 2000-04-20 |
|||||||||||
| 出版者 | ||||||||||||
| 出版者 | Institute of Electronics, Information and Communication Engineers | |||||||||||
| 言語 | en | |||||||||||
| ISSN | ||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||
| 収録物識別子 | 0916-8508 | |||||||||||
| item_10001_source_id_32 | ||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||
| 収録物識別子 | AA10826239 | |||||||||||
| 出版タイプ | ||||||||||||
| 出版タイプ | VoR | |||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||
| 内容記述 | ||||||||||||
| 内容記述タイプ | Other | |||||||||||
| 内容記述 | 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. | |||||||||||
| 言語 | en | |||||||||||
