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

• 岡本 吉央

• ステファン ランガマン

書誌事項

タイトル別名

• Planar Convex Hulls Against Lies

抄録

平面に与えられた n 点から成る集合の凸包を計算する問題を考える．しかし，計算において，高々 e 回の基本演算における間違いが存在する可能性があるものとする．この設定において，計算量が O(n log h+ne log log h) となるアルゴリズムを与える．ただし，h は凸包の端点数である．また，この問題に対して Ω(n log h + ne) という計算量の下界も与える．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.

収録刊行物

• 研究報告アルゴリズム（AL）

  研究報告アルゴリズム（AL） 2011 (8), 1-3, 2011-05-09

詳細情報

• CRID: 1572543026893372800
• NII論文ID: 110008583106
• NII書誌ID: AN1009593X
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles
  • KAKEN