3次元ボロノイ図構成のための数値的に安定な逐次添加法

• Item type: Journal(1)
• 公開日: 1994-01-15
• タイトル: 3次元ボロノイ図構成のための数値的に安定な逐次添加法
• タイトル / 言語: en
• タイトル: Robust Algorithm for Incremental Construction of Three - Dimensional Voronoi Diagrams
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 基礎理論
• 著者所属: 豊田工業高等専門学校情報工学科
• 著者所属: 東京大学工学部計数工学科
• 著者所属: 名古屋大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Information and Computer Engineering, Toyota College of Technology
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Information Engineering, Faculty of Engineering, Nagoya University
• 著者名: 稲垣, 宏; 杉原, 厚吉; 杉江, 昇
• 著者名(英): Hiroshi, Inagaki; Kokichi, Sugihara; Noboru, Sugie
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 幾何図形を扱う効率のよいアルゴリズムが多く提案されているが、それらは数値誤差が発生しないという仮定のもとでのみ正しさが証明されたものであるため、計算機プログラムに翻訳すると計算誤差のために正しく動作しないことがある。本諭文では3次元ボロノイ図を対象とし、これを構成するアルゴリズムの数値的安定化を試みた。従来のアルゴリズムが破綻するのは、誤差を含んだ数値計算結果を信用し遇ぎるためであることを反省し、ここでは、計算誤差を含む数値判定より幾何図形の持つべき位相構造の保持を優先させた。本方針に基づいたアルゴリズムを設計し、それを実際に計算機ヘインプリメントして計算機実験によりその振舞いを観察した。その緒果、従来の算法ではほとんどの場合に処理が破綻をきたすような悪条件の入力に対しても、位相的に矛盾のない緒果が出力されることが確かめられ、その数値的安定性が実証された。
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 35, 号 1, p. 1-10, 発行日 1994-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764