幾何的アルゴリズムの簡易な退化解除法

• Item type: SIG Technical Reports(1)
• 公開日: 1996-09-13
• タイトル: 幾何的アルゴリズムの簡易な退化解除法
• タイトル / 言語: en
• タイトル: An Easy Method to Remove Degeneracies in Computational Geometry
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学工学系研究科
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, University of Tokyo
• 著者名: 今井, 敏行
• 著者名(英): Toshiyuki, Imai
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 幾何的アルゴリズムは誤差がないものとしても退化時に破綻する．すべての退化に対処することはアルゴリズムの考案や実装を困難にする．この困難に対して，既存のアルゴリズムでの退化の統一的な扱い方が研究されてきた．本論文では，幾何的アルゴリズム中で退化入力を統一的な扱う方法を提案する．従来の方法があらかじめアルゴリズムを調べ，退化に備えてアルゴリズムを書き改めておくのに対して，本論文で提案する方法は，退化時に必要なデータをアルゴリズム実行時に計算していく．そのため，計算速度で利点はないが，実装プログラムに対して基本的に変更がいらず，簡単に適用できるという利点がある．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Geometric algorithms sometimes fail in the degenerate cases even without numerical errors. It is difficult to make or imprement an algorithm which can treat any degenerate cases. To reduce the difficulty, some methods how to treat degeneracy systematically were proposed. In this paper, we present a method to treat degenerate inputs systematically in Geometric algorithms. It computes data which is required in degenerate case when executing the algorithm, while conventional methods adapt the algorithm as preprocess to treat the degeneracy. That's why it has no merit of execution time but it is easy to apply the already impremented program without changing the algorithm essentially.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 89(1996-AL-053), p. 102-110, 発行日 1996-09-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会