点集合の強凸－包含包を求めるアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 1996-09-13
• タイトル: 点集合の強凸－包含包を求めるアルゴリズム
• タイトル / 言語: en
• タイトル: Constructing A Strongly Convex Superhull of points
• 言語: 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
• 著者所属(英): en
• 著者所属(英): Department of Electrical and Computer Engineering Nagoya Institute of Technology
• 著者名: 陳, 慰; トウ, ショウブン; 和田, 幸一; 川口, 喜三男
• 著者名(英): Wei, Chen; Xiao, WenDeng; Koichi, Wada; Kimio, Kawaguchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Sをサイズnの平面上の点集合とするとき，Sの〓?強凸?包含包はSの凸包を拡張したもので，次の条件を満たす凸多角形Pである：(）Pはn個以下の頂点を持つ，(）PはSの全ての点を含む，(）Pの各頂点はSの凸包との距離はd以下である，(）Pの各頂点が距離〓以内を移動してもPが凸のままである．本研究では，Sの〓?強凸?包含包を求める初めてのアルゴリズムを提案する．このアルゴリズムは、任意の〓〓0に対して，O( log )時間でSの4〓?強凸?包含包を求める．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let S be a set of n points in the plane and CH(S) be the convex hull of S. We introduce a new concept of strongly convex approximate hulls called 〓-strongly convex δ-superhull, which is a convex polygon P satisfying the following conditions: (1) P has at most n vertices, (2) P contains all the points of S, (3) no vertex of P lies farther than δ outside the convex hull of S, and (4) P remains convex even if its vertices are perturbed by as much as 〓. In this paper, we present the first method for solving such a generalized convex hull problem. We show that an 〓-strongly convex 4〓-superhull can be constructed in O(n log n) time for any 〓〓0.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 89(1996-AL-053), p. 71-78, 発行日 1996-09-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会