間違えても大丈夫な凸包構成アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2011-05-09
• タイトル: 間違えても大丈夫な凸包構成アルゴリズム
• タイトル / 言語: en
• タイトル: Planar Convex Hulls Against Lies
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属: ブリュッセル自由大学
• 著者所属(英): en
• 著者所属(英): Japan Advanced Institute of Science and Technology
• 著者所属(英): en
• 著者所属(英): Universite Libre de Bruxelles
• 著者名: 岡本, 吉央; ステファン, ランガマン
• 著者名(英): Yoshio, Okamoto; Stefan, Langerman
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平面に与えられた n 点から成る集合の凸包を計算する問題を考える．しかし，計算において，高々 e 回の基本演算における間違いが存在する可能性があるものとする．この設定において，計算量が O(n log h+ne log log h) となるアルゴリズムを与える．ただし，h は凸包の端点数である．また，この問題に対して Ω(n log h + ne) という計算量の下界も与える．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Consider the problem of computing the convex hull of a given set of n points in the plane, while at most e errors can occur during the computation. Under this setup, we provide an algorithm running in O(n log h + ne log log h) time, where h is the number of extreme points of the convex hull. Further, we give a lower bound of Ω(n log h + ne) for this problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2011-AL-135, 号 8, p. 1-3, 発行日 2011-05-09
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会